题目训练网址（密码hpuacm） https://vjudge.net/contest/240634#overview 关于同余定理及其性质的介绍参考这篇博文 https://blog.csdn.net/codeharvest/article/details/70314593 关于逆元以及求解逆元的扩展欧几里得算法的介绍参考这篇博文  https://blog.csdn.net/stray_lambs/article/details/52133141 同余定理：两个整数同时除以一个整数所得余数相同，则二整数同余。记作a ≡ b(mod m)。 总的来说同于定理有两点常用 1. 和的取余等于取余的和的取余      (a + b) % m = (a % m + b % m) % m 2. 乘积的取余等于取余的乘积取余  (a * b) % m = ((a % m) * (b % m)) % m 证明： 1 设 a = k1 * m + r1，b = k2 * m + r2
则 (a + b) % m = ((k1 * m + r1) + (k2 * m + r2)) % m
               = ((k1 + k2) * m + (r1 + r2)) % m
               = (r1 + r2) % m
               = (a % m + b % m) % m
所以 (a + b) % m = (a % m + b % m) % m 证明： 2 设 a = k1 * m + r1，b = k2 * m + r2
则 (a * b) % m = ((k1 * m + r1) * (k2 * m + r2)) % m
               = (k1 * k2 * m^2 + (k1 * r2 + k2 * r1) * m + r1 * r2) % m
               = (r1 * r2) % m
               = ((a % m) * (b % m)) % m
所以 (a * b) % m = ((a % m) * (b % m)) % m 逆元与扩展欧几里得算法 逆元：如果 a*x ≡ 1(mod m)，这里我们称x是a关于m的乘法逆元。这怎么求？可以等价于这样的表达式： a*x + m*y = 1，这样用下文的exgcd算法求解出来的x就是a关于m的乘法逆元 a*x≡1(mod m) 等价于a*x+m*y=1 可以用扩展欧几里得求
得一组解，（x+m)mod m即为a的逆元 设c是b的逆元，则有b*c≡1(mod m)
推论：(a/b)mod m 
     = (a/b)*1mod m
     = (a/b)*b*c mod m
     = a*c(mod m) 即a/b的模等于a*(b的逆元)的模 算法代码实现 int exgcd( int a, int b, int &x, int &y ) // 求出来的x是a关于b的逆元 { if( b == 0 ) { x = 1; y = 0; return a; // 最大公约数 } int r = exgcd( b, a%b, x, y ); // 这里的x，y就是x2，y2， 这是第二个方程 int t = x; x = y; y = t - (a/b)*y; return r; // 返回值是a和b的最大公约数 } a*x+b*y=m a*x1+b*y1=gcd(a,b), b*x2 +(a%b)* y2=gcd(b,a%b) 解 x，y的方法的理解：   1、显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；   也就是1*a+0*b = a   2、设 ax1+by1=gcd(a,b); 　　        在下一个exgcd里bx2+(a mod b)y2=gcd(b,a mod b); 　　        根据欧几里德原理有 gcd(a,b)=gcd(b,a mod b); 　　        则:ax1+by1=bx2+(a mod b)y2; 　　        即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2; 　　        根据恒等定理得：x1=y2; y1=x2-(a/b)*y2;         这样我们就得到解 x1,y1 的方法：x1，y1 的值基于 x2，y2。 题目讲解：A青蛙的约会 这道题我们分析在一个数轴上有两只青蛙，这个数轴是首尾交接的，所以可以一直围着它走，显然我们可以列出一个方程来。设它们走了t步，和他们追击了k圈，也就是围着又走了k圈。 
所以 x + m * t = y + n * t + k * L。 
我们转换一下方程： 
(n - m) * t + L * k = x - y
所以它是形如ax+by=c这种形式，我们直接用欧几里得求出一组解输出最小正解就好了。  #include using namespace std; typedef long long LL; 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 ); LL t = x; x = y; y = t - (a/b) * y; return r; } int main() { LL a, b, m, n, l; LL x, y; scanf("%lld%lld%lld%lld%lld", &a, &b, &m, &n, &l ); // 所求方程 (n - m) * t + L * k = a - b t相当于x，k相当于y，两个自变量 LL c = a - b; LL d = exgcd( n-m, l, x, y ); // d为n-m与l的最大公约数 if( c%d !=0 ) // 无解的条件 printf("Impossible "); else { x = x * c /d; // 之前求出的x是所求方程右边是gcd时的x，乘上c除以的正好得到了右边是a-b时的x y = y * c /d; x = (x%l + l) % l; // 求的最小的正数x printf("%lld ", x ); } return 0; }