同余方程，不定方程总结
听说这是数论中比较重要的部分了，一点点的总结吧。。
一.线性同余方程与不定方程：
long long exgcd(long long a,long long b,long long &x,long long &y) { if(!b) { x=1; y=0; return a; } long long tt=exgcd(b,a%b,x,y); long long t; t=x; x=y; y=(t-a/b*y); return tt; }
View Code
单个一元线性方程
求解方法：扩展欧几里得 exgcd
模板：
原理：对于整数 a，b
。存在 x，y使 x*a+y*b=gcd(a,b)；
当b=0时，有gcd(a,b)=a，显然此时 x=1，y=0.
exgcd算法可以在朴素 gcd 中的一步一步的递归中迭代更新 x，y的值，最终求出 x*a+y*b=gcd(a,b)的一组解。
利用exgcd求不定方程 x*a+y*b=c 解的步骤：
（1）.用 exgcd求出 d=gcd(a,b) 和 x*a+y*b=gcd(a,b) 一组解 x0，y0 ;
（2）.判断 c%d==0，则有解，否则无解
（3）.令 x=x0*c/d，y=y0*c/d；则得到此方程的一组解 x，y
（4）.若需要求最大最小解，再线性变换 x，y查找。
例： x*a+y*b=c ，y每增加1，x减小b/a，化为互质整数：y增加a/d，x减小b/d，可见x的周期是b/d
所以要找最小的x 只需要 x=(x%(b/d)+b/d)%(b/d)即可。
求解同余方程 a*x==b mod m，可转化为求 x*a+y*m=b，套用上面的步骤求解即可
例题 poj1061 poj2115
一元一次同余方程组 （x ==ai (mod bi) ）：
朴素解法:
思想：方程的合并，转化为单个同余方程
参考资料 http://www.cnblogs.com/heweiyou1993/p/3301894.html
模板：
int exgcd(int a,int b,int &x,int &y) { if(!b) { x=1; y=0; return a; } int tt=exgcd(b,a%b,x,y); int t; t=x; x=y; y=(t-a/b*y); return tt; } int solve() { int a1,a2,b1,b2,x,y,A,B,C,d,t; a1=a[0]; b1=b[0]; for(int i=1;i<m;i++) { a2=a[i]; b2=b[i]; A=a1; B=a2; C=b2-b1; d=exgcd(A,B,x,y); if(C%d) { return -1; } t=B/d; x=(x*(C/d)%t+t)%t; b1=a1*x+b1; a1=a1/d*a2; } return b1; }
View Code
例题：hdu1573 题解：http://www.cnblogs.com/oneshot/p/3986633.html
中国剩余定理：
在同余方程组x==ai mod bi 中，如果 bi互质，那么可以通过中国剩余定理快速求解
模板：
int exgcd(int a,int b,int &x,int &y) { if(b==0) { x=1;y=0; return a; } int r=exgcd(b,a%b,x,y); int t=x; x=y; y=(t-a/b*y); return r; } int china(int n) { int M=1; int ans=0; int x,y,d; for(int i=0;i<n;i++) { M*=m[i]; } for(int i=0;i<n;i++) { int mi=M/m[i]; int x,y; d=exgcd(mi,m[i],x,y); ans=(ans+a[i]*mi*x)%M; } while(ans<0) ans+=M; return ans; }
View Code
例题：poj1006 题解：http://www.cnblogs.com/oneshot/p/3986679.html
多元线性同余方程组：
暂时还没有做过这种题 先不看了
二.高次同余方程组
形式：
A^X mod C =B
三.特殊的不定方程
费马大定理
内容：
方程x^n+y^n=z^n 当n>=3时无非0整数解。。
毕达哥拉斯三元组
毕达哥拉斯定理就是勾股定理 x2+y2=z2；
满足 gcd(x,y,z)=1的 称为本源毕达哥拉斯三元组
本源三元组满足 x=m2-n2; y=2mn; z=m2+n2 其中 m,n不同奇偶
我们在求所有三元组的时候只需要先求出本源三元组即可。
例题： poj 1305（概念题）http://www.cnblogs.com/oneshot/p/3990978.html
佩尔方程
形式：
x^2-d*y^2=1 （d>1 && d不为完全平方数）
设最小特解 x0,y0
则有迭代公式 xn=xn-1 * x0 +d*yn-1*y0
yn=xn-1 * y0 +yn-1 * x0
得到最小特解（暴力）后 可以用矩阵快速幂求所有解
先挖坑，矩阵刷了再回来填。。
例题poj 1320 hdu 3292