预备定理（整除）：
. 如果a|b，且b|c，那么a|c
2. a|b且a|c等价于对任意的整数x和y，由a|(a*x+c*y)
3. 设m!=0，那么a|b等价于(m*a)|(m*b)
4. 设整数x和y满足下式a*x+b*y=1，且a|n、b|n，那么(a*b)|n
证明：
因为a|b且b|n
根据性质3可得:(a*b)|(b*n)且(a*b)|(a*n)
再由性质2可得:(a*b)|(a*n*x+b*n*y)
其中:a*n*x+b*n*y=n*(a*x+b*y)=n*1=n 所以:(a*b)|n
5. 若b=q*d+c，那么d|b的充要条件是d|c
整除在c++中就是%
扩展欧几里得(求同余方程)
应用性质：
对于不完全为0的整数a，b存在a*x+b*y==gcd(a,b)
化简式子：
使a为两数中较大的数
当b==0时，gcd(a,b)==gcd(a,0)==a
所以当b==0时，x==1，y==0
同时，ax+by==gcd(a,b),bx1+a%by1==gcd(a,a%b)
所以，ax+by==bx1+(a-a/b*b)*y1;
ax+by==bx1+ay1-a/b*b*y1
ax+by==ay1+(x1-a/b*y1)
即:
x==y1,y==x1-a/b*y1
由此可得出扩展欧几里得求x，y的递归式
核心代码：
1 int exgcd(int a,int b,int &x,int &y)
2 {
3 if(b==0)
4 {
5 x=1,y=0;
6 return a;
7 }
8 int r=exgcd(b,a%b,x,y),tmp;
9 tmp=x,x=y,y=tmp-a/b*y;
10 return r;
11 }
例一：
codevs 1200
求关于 x 同余方程 ax ≡ 1 (mod b)的最小正整数解。
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 int x,y;
5 int gcd(int a,int b,int &x,int &y)
6 {
7 if(b==0)
8 {
9 x=1;
10 y=0;
11 return a;
12 }
13 int r=gcd(b,a%b,x,y);
14 int tmp=0;
15 tmp=x;
16 x=y;
17 y=(tmp-(a/b)*y);
18 return r;
19
20 }
21 int main()
22 {
23 int a,b;
24 cin>>a>>b;
25 int r=gcd(a,b,x,y);
26 while(x<0)
27 {
28 x=b+x;
29 }
30 cout<<x;
31 return 0;
32 }
View Code
例二
poj1061
http://poj.org/problem?id=1061
青蛙问题
该题是扩展GCD的应用，即利用GCD的辗转相除法来解 一个二元一次 不定式，当然也是利用了回代的思想，具体原理参阅百度百科 “扩展欧几里德算法" ,对于一个不定方程肯定有N组解，
该题就是要找到一个满足方程的步数（其中的一个变量 x）的最小整数解，注意要用 long long int。
求解线性同余方程 exgcd
定理1:
对于方程a*x+b*y=c,该方程等价于a*x ≡c(mod b)
有整数解的充分必要条件是:c%gcd(a,b)=0
根据定理1,对于方程a*x+b*y=c,我们可以先用exgcd求出一组x0,y0
也就是a*x0+b*y0=gcd(a,b),然后两边同时除以gcd(a,b),再乘以c
这样就得到了方程a*x0*c/gcd(a,b)+b*y0*c/gcd(a,b)=c
我们也就得到了方程的一个解
定理2:
若gcd(a,b)=1,且x0,y0为a*x+b*y=c的一组解
则该方程的任一解可表示为:x=x0+b*t,y=y0-a*t
且对于任一整数t,皆成立.
根据定理2,可以求出方程的所有解.
但是实际问题中,我们往往被要求去求最小整数解
也就是求一个特解x
t=b/gcd(a,b),x=(x%t+t)%t
核心代码
-
1 bool Linear_Equation(int coeA,int coeB,int coeC,int &ansX,int &ansY)
2 {
3 int pos=Extended_Eucl