线性同余方程
定义：形如 ax ≡ b (mod c)的方程被称为线性同余方程。
求解方法：线性同余方程可以通过两个定理求解得出答案：
定理1：
方程 ax + by = c 与方程 ax ≡ b ( mod c )是等价的，有整数解的充要条件是 gcd( a, b ) | c，即ab的最大公约数可以整除c 。
通过定理1我们可以通过exgcd求出一组解 x0,y0 ，然后两边同时除以gcd(a , b),再乘以c。然后就得到了方程 a*c*x0/gcdc(a , b) + b*c*y0/gcd(a, b) = c .这样我们就得出了方程的一个解。
定理2：
若 gcd(a, b) = 1，且 x0, y0 为方程 ax + by = c 的一组解，则该方程的任意解可表示为: x=x0 + bt, y= y0+ at , 且对任意整数 t 都成立。
根据定理2 ，我们可以求出方程所有的解 ，但在实际问题中，我们通常被要求求出一个最小整数解，也就是一个特解x , t = b/gcd(a, b), x = (x mod t +t) mod t 。即为最小整数解。
模板代码：
int ex_gcd(int a, int b, int& x, int& y)
{
if (b == 0) {
x = 1;
y = 0;
return a;
}
int d = ex_gcd(b, a % b, x, y);
int temp = x;
x = y;
y = temp - a / b * y;
return d;
}
bool liEu(int a, int b, int c, int& x, int& y) //将扩展欧几里德封装进函数。
{
int d = ex_gcd(a, b, x, y);
if (c % d != 0) return 0;
int k = c / d;
x *= k;
y *= k;
return 1;
}
if(!liEu(a,b,c,x,y)) cou<<"No answer"<<endl;
else cout<<x<<" "<<y<<endl;