扩展欧几里得
互质的两个数a和b，不能用ax+by（x、y为非负整数）的形式表示出的最大整数是a*b-a-b
a和b不互质的情况下，ax+by = k*gcd(a,b)，其中gcd(a,b)>1。那么在k无限大的情况下，不能表示的数就有无限多个，没有最大整数的存在。
互质时，原文
a或者b是1的情况下容易证明. 以下情况都是a>1且b>1的情况. 首先证明ab-a-b不能表示成ax+by 假设ab-a-b=ax+by,那么ab=am+bn (m,n都大于等于1) 左边是a的倍数,右边am是a的倍数,那么要求bn也要是a的倍数 b不是a的倍数,只能要求n是a的倍数,这样的话,bn=bn'a>=ba 那么am=ab-bn所以am1矛盾. 接着证明ab-a-b+i能表示成ax+by(i>0) 因为ab互质,最大公约数就是1,根据辗转相减的方法知ma+nb=1, 不妨假设m>0,n1(m=0意味着nb=1不可能的),所以ab-a-b+i(ma+nb)=(im-1)a+(a+in-1)b im-1>0,现在只要证明a+in-1>=0,因为ima+inb=i 如果,|in|>ja其中j>0,那么ima=i+|in|b>jab,所以im>jb 所以ima+inb=(im-jb)a-(|in|-ja)b=i,说明|in|>ja时,我们就能调整im,in使得|in|
定理：
a和b互质时，当c>a*b-a-b时，ax+by=c有非负解。
这个题的题设默认两个数就是互质的。233
#include <iostream> #include <cstring> #include <cstdlib> #include <vector> #include <cmath> #include <algorithm> #include <set> #include <queue> #include <string> #include <map> #include <stack> #define MAXN 1000004 #define MOD 1000000009 #define INF 0x7ffffff #define lowbit(x) (x)&(-x) using namespace std; int gcd(int a,int b){ while(a%=b^=a^=b^=a); return b; } int main(){ int a,b; cin >> a >> b; if(gcd(a,b) == 1){ cout << a*b-a-b << endl; } else cout << "Zhe ti ye tai xiu le ba" << endl; }
