因为方法本身比较死所以就直接上代码吧。

#include using namespace std; //扩展欧几里得算法 int extended_gcd(int a, int b, int &x, int &y) { if (b == 0) { x = 1; y = 0; return a; } int r = extended_gcd(b, a % b, x, y); int t = x; x = y; y = t - a / b * y; return r; } //用扩展欧几里得解模线性方程ax=b (mod n) bool modularLinearEquation(int a, int b, int n) { int x, y, x0, i; int d = extended_gcd(a, n, x, y); //ax=b (mod n) 等价于ax+ny=b if (b%d) return false; x0 = x*(b / d) % n; for (i = 1; i <= d; i++) printf("%d ", (x0 + i*(n / d)) % n); return true; } int main() { int a, n; while (cin >> a >> n) { modularLinearEquation(a, 1, n); } return 0; }

以【生理周期】一题为例可以简单了解一下运用。
Description 人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天，人会在相应的方面表现出 {MOD}。例如，智力周期的高峰，人会思维敏捷，精力容易高度集中。因为三个周期的周长不同，所以通常三个周期的高峰不会落在同一天。对于每个人，我们想知道何时三个高峰落在同一天。对于每个周期，我们会给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）。你的任务是给定一个从当年第一天开始数的天数，输出从给定时间开始（不包括给定时间）下一次三个高峰落在同一天的时间（距给定时间的天数）。例如：给定时间为10，下次出现三个高峰同天的时间是12，则输出2（注意这里不是3）。 Input 输入四个整数：p, e, i和d。 p, e, i分别表示体力、情感和智力高峰出现的时间（时间从当年的第一天开始计算）。d 是给定的时间，可能小于p, e, 或 i。 所有给定时间是非负的并且小于365, 所求的时间小于21252。 

当p = e = i = d = -1时，输入数据结束。 Output 从给定时间起，下一次三个高峰同天的时间（距离给定时间的天数）。 

采用以下格式： 
Case 1: the next triple peak occurs in 1234 days. 

注意：即使结果是1天，也使用复数形式“days”。 Sample Input 0 0 0 0 0 0 0 100 5 20 34 325 4 5 6 7 283 102 23 320 203 301 203 40 -1 -1 -1 -1 Sample Output Case 1: the next triple peak occurs in 21252 days. Case 2: the next triple peak occurs in 21152 days. Case 3: the next triple peak occurs in 19575 days. Case 4: the next triple peak occurs in 16994 days. Case 5: the next triple peak occurs in 8910 days. Case 6: the next triple peak occurs in 10789 days.
同余方程 ax≡b (modn)对于未知数 x 有解，当且仅当 gcd(a,n) | b。且方程有解时，方程有 gcd(a,n) 个解。
求解方程 ax≡b (modn) 相当于求解方程 ax+ny= b, (x, y为整数)。 此处的乘法逆元可用该法求解： ax≡1（mod n）等价于 ax+ny=1=gcd(a,n)，调用extended_gcd(a,n,x,y)，并当公约数ret=1(a,n互为质数,ret一定等于1)时。 当x>0时,x即为a的乘法逆元。当x<0时,将x转换为mod n的最小正整数即可: 　　　 while(x<0) 　　　　  x+=n; 所以可以直接套用扩展欧几里得算法求解。 回到题目，该题是要解以下方程组： x+d≡p(mod 23) x+d≡e(mod 28) x+d≡i(mod 33) 三个周期互素，所以M=23*28*33=21252， M1=M/23=924 M2=M/28=759 M3=M/33=644   所以根据： M1* t1≡924*t1≡1(mod 23) M2* t2≡759*t2≡1(mod 28) M3* t3≡644*t3≡1(mod 33)   用上述扩展欧几里得算法程序可以得到解分别为： t1=6(mod 23) t2=19(mod 28) t3=2(mod 33)   所以x+d≡(M1* t1*p+ M2*t2*e+ M3* t3*i)(mod 21252) 即：x=(5544*p+14421*e+1288*i-d)%21252 #include using namespace std; int main() { int p, e, i, d, count = 0, x; while (cin >>p>>e>>i>>d,~p)//逗号表达式的值为最后一项的值，而-1和0的补码形式刚好是各位取反 { x = (5544 * p + 14421 * e + 1288 * i - d + 21252) % 21252;//之前得到的式子 if (x == 0) x = 21252; cout << "Case " << ++count << ": the next triple peak occurs in " << x << " days." << endl; } return 0; }

来源和参考： http://blog.csdn.net/synapse7/article/details/9946013 http://www.cnblogs.com/Seiyagoo/archive/2012/03/21/2410369.html https://xuanwo.org/2015/03/11/number-theory-gcd/
【代码来源于网络，仅作个人学习用，如有侵权我会删除】