题意:
给定a,b且a,b互质
求\(ax+by(x,y\ \epsilon\ N)\)不能表示的最大数解法:
说实话,这道题挺chao简ji单nan……
设a<b答案为x
若\(x\equiv ma\ (mod\ b)\ (0\le m<b)\)
则\(x=ma+nb\ (0\le m<b)\)
若\(n\ge 0\)则x可以用a,b表示
所以x不能用a,b表示且最大时\(n=-1,m=b-1\)
所以\(x=a\times (b-1)-b=a\times b-a-b\)
代码:
#include#include #include #include #include #define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)<(y)?(x):(y))#define rep(i,a,b) for(int i=(a);i<=(b);++i)#define dwn(i,a,b) for(int i=(a);i>=(b);--i)using namespace std;typedef long long ll;int a,b;int main(){ scanf("%d%d",&a,&b); printf("%lld",1ll*a*b-a-b); return 0;}