取模： 先说一点，就是取模运算n%p的结果与p的符号无关，由n决定。 例如：7%4=3,-7%4=-3,7%-4=3，-7%-4=-3；
扩展欧几里德定律：　 对于不完全为0的非负整数a，b，gcd(a, b)表示a, b的最大公约数，必定存在整数对x，y，满足a*x+b*y==gcd(a, b)。 证明：(转) a*x1+b*y1=gcd(a, b);  b*x2+(a%b)*y2=gcd(b, a%b); 因为由欧几里德定理知：gcd(a, b)==gcd(b, a%b) 所以a*x1+b*y1=b*x2+(a%b)*y2;   　　因为r=a%b,   r =a-k*b所以==> a*x1+b*y1=b*x2+(a-k*b)*y2;       　　因为k=a/b;所以　==> a*x1+b*y1=b*x2+(a-(a/b)*b)*y2;   　　展开得到　　==>　　　　 a*x1+b*y1=b*x2+a*y2-b*(a/b)*y2;　　转换得到      ==>
a*x1+b*y1=a*y2+b*(x2-(a/b)*y2); 观察上式可知 x1=y2, y1=x2-a/b*y2; 由此可知x1，y1是由x2，y2得出来的，由此类推x2，y2是由x3，y3得出来的， 那什么时候是终止呢？也就是递归gcd(a, b)中b=0时；也就是说此时a的值就是要求得最大公约数 即gcd(a, 0)此时由扩展欧几里得定律a*x+b*y==gcd(a, b) 知 a*x+b*y=a; 解出x=1, y=0; 此时就是递归终止的地方： 扩展欧几里德应用：

CodeForces 7C

求解不定方程；如a*x+b*y=c; 已知a, b, c的值求x和y的值

 a*x+b*y=gcd(a, b)*c/gcd(a, b); 最后转化为 a*x/(c/gcd(a, b))+b*y/(c/gcd(a, b))=gcd(a, b);  最后求出的解x0，y0乘上c/gcd(a, b)就是最终的结果了 x1=x0*c/gcd(a, b); y1=y0*c/gcd(a, b); #include #include #include #include #include #include #define ll long long using namespace std; ll exgcd(ll a, ll b, ll &x, ll &y) { if(b==0) { x=1; y=0; return a; } ll g=exgcd(b,a%b,x,y),t; t=x; x=y; y=t-(a/b)*y; return g;//g是全程不变的，就是a,b的最小公约数。  } int main() { ll a,b,c,x,y; cin>>a>>b>>c; ll t=exgcd(a,b,x,y); if(c%t==0) printf("%lld %lld ",-x*c/t,-y*c/t); else puts("-1"); }
POJ 1061  http://poj.org/problem?id=1061 根据题意可以列出 (x+km)%L=(y+kn)%L ,k为步数，    转换一下得，(m-n)*a+L*b=y-x,求a的最小整数解 扩展欧几里德可以求出一组解，ao，bo； ax+by=gcd(a,b); 求x的最小正整数解 求出来x可能是负的，但是a(x+bn)+b(y-an)=gcd(a,b); 那么xo=x+bn和yo=y-an都能是该方程的解 那么最小的正x则为(x%b+b)%b;------------------- #include #include #include #include #include #include #define ll long long using namespace std; ll exgcd(ll a, ll b, ll &x, ll &y) { if(b==0) { x=1; y=0; return a; } ll r=exgcd(b,a%b,x,y),t; t=x; x=y; y=t-(a/b)*y; return r; } int main() { ll x0,y0,m,n,L,x,y; cin>>x0>>y0>>m>>n>>L; ll a=m-n,c=y0-x0; ll g=exgcd(a,L,x,y); if(c%g!=0) puts("Impossible"); else { x*=c/g; printf("%lld ",(x%L+L)%L); } }
hdoj2669 http://acm.hdu.edu.cn/showproblem.php?pid=2669 求ax＋by＝1 满足方程，且x为最小非负整数的xy。 如果x用exgcd求出来为负数的话，有a(x+bn)+b(y-an)=1; 那么x%b就是最接近0的负数，+b 就为正，再模b即为非负 y同理。 #include #include #include #include #include #include #define ll long long using namespace std; ll exgcd(ll a, ll b, ll &x, ll &y) { if(b==0) { x=1; y=0; return a; } ll r=exgcd(b,a%b,x,y),t; t=x; x=y; y=t-(a/b)*y; return r; } int main() { ll a,b,x,y; while(~scanf("%lld%lld",&a,&b)) { ll g=exgcd(a,b,x,y); if(g==1) { if(x>=0) printf("%lld %lld ",x,y); else printf("%lld %lld ",(x%b+b)%b,(y%a-a)%a); } else puts("sorry"); } }