辗转相除+中国剩余定理含代码Word下载.docx

辗转相除+中国剩余定理含代码Word下载.docx

《辗转相除+中国剩余定理含代码Word下载.docx》由会员分享，可在线阅读，更多相关《辗转相除+中国剩余定理含代码Word下载.docx（11页珍藏版）》请在冰点文库上搜索。

实验要求：

（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

3.2程序核心代码

#include<

iostream>

#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&

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（a,b）;

x=s2;

y=t2;

intcrt（）//孙子定理解线性同余方程

LLA[len],M[len],l;

inti,j;

printf（"

CRT（n）:

\n"

）;

scanf（"

%I64d"

&

l）;

for（i=0;

i<

l;

++i）scanf（"

%I64d%I64d"

A[i],&

M[i]）;

l-1;

++i）

for（j=i+1;

j<

++j）

if（gcd（M[i],M[j]）!

=1）

Marrayunsatisfiedco-primecondition!

\n\n"

return-1;

LLd,x,y,m,n=1,ans=0;

for（i=0;

++i）n*=M[i];

m=n/M[i];

d=exgcd（M[i],m,x,y）;

ans=（ans+（y*m*A[i]）%n）%n;

d=（n+ans）%n;

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

Pleaseenter2numbersa,b:

（Quitwhena=b=0）\n"

a,&

b）,a*b）//多组数据，a=b=0时完毕处理。

g1=gcd（a,b）;

（%I64d,%I64d）=%I64d\n"

a,b,g1）;

[%I64d,%I64d]=%I64d\n"

a,b,abs（a*b）/g1）;

g2=exgcd（a,b,x,y）;

printf（"

X=%I64dY=%I64d\n"

x,y）;

%I64d*%I64d+%I64d*%I64d=%I64d\n"

x,a,y,b,g2）;

g2=exgcd2（a,b,x,y）;

%I64d*%I64d+%I64d*%I64d=%I64d\n\n"

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和中国剩余定理。

让我感受到了学习的知识、理论，运用于实践，成功解决实际问题的愉悦。