P1082 同余方程
- 数论
0. 导读
数论被誉为数学的皇后，它的研究对象是我们经常接触的整数。 例如：求两个整数的最大公约数和最小公倍数，求一个正整数的素因子分解，求一个方程的整数解等。
1. 整除
设a是非零整数，b是整数。如果存在一个整数q，使得b=a*q ，那么就说b可被a整除，记作a|b，且称b是a的倍数，a是b的约数（因子）
PS：关于整除的一些性质，可参考相关书籍或阅读相关博客。
2. 二元一次不定方程
二元一次不定方程的一般形式为：a x + b y =c。
其中a,b,c是整数，ab≠0。此方程有整数解的充分必要条件是GCD(a,b)|c。
设X,Y是该方程的一组整数解，那么该方程的所有整数可表示为：
x = X + b/GCD(a,b)*t
y = Y - a/GCD(a,b)*t
（证明在下面）
3.扩展欧几里德算法
扩展欧几里得算法是用来在已知（a,b）时，求解一组(p,q)，使得pa+qb = GCD(a,b)
因为 : GCD(a,b) = GCD(b,a%b), a%b = a-a/b*b
所以 : p*a+q*b = GCD(a,b) = GCD(b,a%b) = p*b +q*(a%b) = p*b + q*(a-a/b * b) = q * a +(p-a/b*q)*b，这样它就将a与b的线性组合简化为b与a%b的线性组合。
根据前边的结论：a和b都在减小，当b减小到0时，就可以得出p=1,进而可得q=0，然后递归回去就可以求出最终的p和q了 首先，根据数论中的相关定理，解一定存在。
4.同余
若a,b为两个整数，且它们的差a-b能被某个自然数m所整数，则称a就模m来说同余于b，或者说a和b关于模m同余，记为:a≡b(mod m)。它意味着：a-b = mk (k为某一个整数）
例如：32≡2(mod 5)，转化为二元一次不定方程：32x + 5y = 2.
PS：关于同余的一些性质，可参考相关书籍或阅读相关博客。
5.求解线性同余方程（即求解二元一次不定方程）
定理1：对于方程 ax + by = c，该方程等价于 a*x ≡ c(mod b),有整数解的充分必要条件是：c%GCD(a,b)=0.
根据定理1，对于方程 ax + by =c，我们可以先用扩展欧几里德算法求出一组 x0,y0，也就是ax0 + by0 = GCD(a,b),然后两边同时除以GCD(a,b)，再乘以c。这样就得到了方程
a*x0 * c/GCD(a,b)+b*y0 *c/GCD(a,b) = c
我们也就找到了线性同余方程的一个解X,Y。
X = x0 * c/GCD(a,b)
Y = y0 * c/GCD(a,b)定理2：若GCD(a,b)=1，且X,Y为ax+by=c的一组解，则该方程的任一解可表示为：
a*x0 + b*y0 = c (1)
a*x1 + b*y1 = c (2)
由（1） - （2）可得： a(x0 - x1) = b(y1 - y0) （3）
令gcd(a,b) = g;
（3）/g 得： a/g (x0 - x1) = b/g (y1 - y0)
a/g , b/g 的商数互为质数，
所以b/g 为 (x0 - x1) 的倍数，-a/g 为（y0 - y1）的倍数
x = X + b/g * t
y = Y - a/g * t
且对任一整数t皆成立。根据定理2，可以求出方程的所有解。但实际问题中，我们往往被要求去求最小整数解，也就是求一个特殊解x。
由定理1 得到： x = X + b/g * t (4)
T = b/g
将（4）式进行变形 ： min = (X%T + T)%T 参考资料：通过扩欧得出线性同余方程的通解以及x的最小正整数解
6.同余方程代码
//该问题转换为: a*x + by = 1，求x得最小整数解
#include<iostream>
using namespace std;
int x,y,a,b,m,k; //定义同余方程的各个系数
void exgcd(int a,int b) {
if(b==0){ //递归出口
x=1; y=0;
return ;
}
exgcd(b,a%b);
//系数变化
k=x;
x=y;
y=k-a/b*y;
return ;
}
int main() {
cin>>a>>b;
exgcd(a,b);
cout<<(x%b+b)%b;
return 0;
}7.相关题型：
P1516 青蛙的约会