辗转相除+中国剩余定理(含代码)

1、. .实验一：辗转相除法及其应用姓 名： 周伟康 学 号：班 级： 信息平安11-1 实验地点：三机房 实验时间：2012/11/23- 优选. .1 实验目的和要求实验目的：掌握用欧几里德算法实现最大公约数、最小公倍数；掌握a模m的逆的求解方法；掌握用中国剩余定理求解线性同余方程组。实验要求： (1).利用欧几里得算法求解两个数的最大公约数。(2).利用欧几里得算法求解两个数的最小公倍数。(3).利用中国剩余定理求解线性同余方程组2 实验环境和工具Microsoft Visual C+3 实验结果3.1 求逆算法的流程图开场a, m互质？aa 1 (mod m)求a 流程图。 t2 = 1;

2、t1 = 0;m | a ？q = a / m;t1 -= q * t2;a %= m;swap(t1, t2);swap(a, m);输入 a ， m输出t2即a完毕NYN3.2 程序核心代码#include <iostream>#define LL _int64#define len 100using namespace std;LL gcd(LL a, LL b) / Eucild if (a%b) return gcd(b, a%b);return b;LL exgcd(LL a, LL b, LL &x, LL &y) /扩展欧几里德，递归实现。 if (

3、!b)x = 1;y = 0;return a;LL g = exgcd(b, a%b, x, y);LL t = x; x = y; y = t-(a/b)*y;return g;int exgcd2(LL a, LL b, LL &x, LL &y) /扩展欧几里德，递推实现。LL q, s1, s2, t1, t2;s1 = t2 = 1;s2 = t1 = 0;while (a % b) q = a / b;s1 -= q * s2;t1 -= q * t2;a %= b;swap(s1, s2);swap(t1, t2);swap(a, b);x = s2; y =

4、t2;return b;int crt() / X子定理解线性同余方程LL Alen, Mlen, l;int i, j; printf("CRT (n): n"); scanf("%I64d", &l); for (i=0;i<l;+i) scanf("%I64d %I64d", &Ai, &Mi); for (i=0;i<l-1;+i) for (j=i+1;j<l;+j) if (gcd(Mi, Mj)!=1) printf("M array unsatisfied co-pr

5、ime condition!nn");return -1; LL d, x, y, m, n=1, ans=0;for (i=0;i<l;+i) n *= Mi; for (i=0;i<l;+i) m = n / Mi;d = exgcd(Mi, m, x, y); ans = (ans + (y * m * Ai) % n) % n; d = (n + ans) %n; printf("Minimun X = %I64dnn", d);int main() LL a, b; LL g1, g2, x, y;int c; while (printf(&

6、quot;Press '1' for Euclid， '2' for Chinese reminder theory.n"),scanf("%d", &c), c=1 | c=2) if (c=2) crt(); else while (printf("Please enter 2 numbers a, b : (Quit when a=b=0)n"),scanf("%I64d %I64d", &a, &b),a*b) / 多组数据，a=b=0时完毕处理。 g1 = g

7、cd(a, b); printf("(%I64d, %I64d) = %I64dn", a, b, g1); printf("%I64d, %I64d = %I64dn", a, b, abs(a*b)/g1);g2 = exgcd(a, b, x, y);printf("X = %I64d Y = %I64dn", x, y); printf("%I64d * %I64d + %I64d * %I64d = %I64dn", x, a, y, b, g2);g2 = exgcd2(a, b, x, y);prin

8、tf("%I64d * %I64d + %I64d * %I64d = %I64dnn", x, a, y, b, g2); system("pause"); return 0;3.3 运行结果及分析1a = 18 ，b = 12 时，gcda，b= 6，lcma，b= 36。且有x = 1，y = -1 时，ax + by = gcd(a,b) 成立。结果正确 2a = -1859，b = 1573时，gcda，b= 143 ，lcma，b= 20449。且有x = 5，y = 6 时，ax + by = gcd(a,b) 成立。结果正确 3a =169，b = 121时，gcda，b= 1 ，lcma，b= 20449。且有x = 58，y = -81 时，ax + by = gcd(a,b) 成立。结果正确 4a =46480，b = 39423时，gcda，b= 1 ，lcma，b= 1832381040。且有x = 16720，y = -19713 时，ax + by = gcd(a,b) 成立。结果正确 5a =737，b = 635时，gcda，b= 1 ，lcma，b= 467995。且有x = 193，y = -224 时，ax + by = gcd(a,b) 成立。结果正确 6 78 9910