辗转相除+中国剩余定理含代码.docx
- 文档编号:4921149
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:11
- 大小:140.72KB
辗转相除+中国剩余定理含代码.docx
《辗转相除+中国剩余定理含代码.docx》由会员分享,可在线阅读,更多相关《辗转相除+中国剩余定理含代码.docx(11页珍藏版)》请在冰点文库上搜索。
辗转相除+中国剩余定理含代码
实验一:
辗转相除法及其应用
姓名:
周伟康
学号:
班级:
信息平安11-1
实验地点:
三机房
实验时间:
2012/11/23
1实验目的和要求
实验目的:
掌握用欧几里德算法实现最大公约数、最小公倍数;掌握a模m的逆的求解方法;掌握用中国剩余定理求解线性同余方程组。
实验要求:
(1).利用欧几里得算法求解两个数的最大公约数。
(2).利用欧几里得算法求解两个数的最小公倍数。
(3).利用中国剩余定理求解线性同余方程组
2实验环境和工具
MicrosoftVisualC++
3实验结果
3.1求逆算法的流程图
开场
a,m互质?
aa’≡1(modm)
求a’流程图。
t2=1;
t1=0;
m|a?
q=a/m;
t1-=q*t2;
a%=m;
swap(t1,t2);
swap(a,m);
输入a,m
输出t2〔即a’〕
完毕
N
Y
N
3.2程序核心代码
#include
#defineLL__int64
#definelen100
usingnamespacestd;
LLgcd(LLa,LLb)//Eucild
{
if(a%b)returngcd(b,a%b);
returnb;
}
LLexgcd(LLa,LLb,LL&x,LL&y)//扩展欧几里德,递归实现。
{
if(!
b)
{
x=1;
y=0;
returna;
}
LLg=exgcd(b,a%b,x,y);
LLt=x;x=y;y=t-(a/b)*y;
returng;
}
intexgcd2(LLa,LLb,LL&x,LL&y)//扩展欧几里德,递推实现。
{
LLq,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=t2;
returnb;
}
intcrt()//孙子定理解线性同余方程
{
LLA[len],M[len],l;
inti,j;
printf("CRT(n):
\n");
scanf("%I64d",&l);
for(i=0;i for(i=0;i for(j=i+1;j if(gcd(M[i],M[j])! =1) { printf("Marrayunsatisfiedco-primecondition! \n\n"); return-1; } LLd,x,y,m,n=1,ans=0; for(i=0;i for(i=0;i { m=n/M[i]; d=exgcd(M[i],m,x,y); ans=(ans+(y*m*A[i])%n)%n; } d=(n+ans)%n; printf("MinimunX=%I64d\n\n",d); } intmain() { LLa,b; LLg1,g2,x,y; intc; while(printf("Press'1'forEuclid,'2'forChineseremindertheory.\n"),scanf("%d",&c),c==1||c==2) { if(c==2)crt();else while(printf("Pleaseenter2numbersa,b: (Quitwhena=b=0)\n"),scanf("%I64d%I64d",&a,&b),a*b)//多组数据,a=b=0时完毕处理。 { g1=gcd(a,b); printf("(%I64d,%I64d)=%I64d\n",a,b,g1); printf("[%I64d,%I64d]=%I64d\n",a,b,abs(a*b)/g1); g2=exgcd(a,b,x,y); printf("X=%I64dY=%I64d\n",x,y); printf("%I64d*%I64d+%I64d*%I64d=%I64d\n",x,a,y,b,g2); g2=exgcd2(a,b,x,y); printf("%I64d*%I64d+%I64d*%I64d=%I64d\n\n",x,a,y,b,g2); } } system("pause"); return0; } 3.3运行结果及分析 〔1〕a=18,b=12时,gcd〔a,b〕=6,lcm〔a,b〕=36。 且有x=1,y=-1时,ax+by=gcd(a,b)成立。 结果正确 〔2〕a=-1859,b=1573时,gcd〔a,b〕=143,lcm〔a,b〕=20449。 且有x=5,y=6时,ax+by=gcd(a,b)成立。 结果正确 〔3〕a=169,b=121时,gcd〔a,b〕=1,lcm〔a,b〕=20449。 且有x=58,y=-81时,ax+by=gcd(a,b)成立。 结果正确 〔4〕a=46480,b=39423时,gcd〔a,b〕=1,lcm〔a,b〕=1832381040。 且有x=16720,y=-19713时,ax+by=gcd(a,b)成立。 结果正确 〔5〕a=737,b=635时,gcd〔a,b〕=1,lcm〔a,b〕=467995。 且有x=193,y=-224时,ax+by=gcd(a,b)成立。 结果正确 〔6〕 〔7〕 〔8〕 〔9〕 〔9〕 〔10〕 〔11〕 4思考题〔可选〕 通过以上程序验证解为537140的同余方程组: 假设运行结果不正确,思考如何修改程序。 运行正确。 5实验心得 本次实验,深化理解并实现了辗转相除、扩展Euclid和中国剩余定理。 让我感受到了学习的知识、理论,运用于实践,成功解决实际问题的愉悦。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 辗转 中国 剩余 定理 代码