@Lin--
2018-09-17T07:16:40.000000Z
字数 1539
阅读 292
计算机数学
#欧几里得算法
#迭代
def gcd(a,b):
while b!=0:
y=b
b=a%b
a=y
return a
def egcd(a,b):
r0,r1,s0,s1=1,0,0,1
while b:
q,a,b=a//b,b,a%b
r0,r1=r1,r0-q*r1
s0,s1=s1,s0-q*s1
return a,r0,s0
返回值a是a与b最大公倍数,r0,s0分别为等式 的系数,
根据欧几里得算法有
得
上述代码运算过程为:
#a*x=N*y1+p(p是余数) ①;b=N*y2+p(p是余数) ②
#有p=b-N*y2;带入①式a*x=N*y1+b-N*y2;得:a*x-(y1+y2)*N=b,即a*x+y*N=b;
#b必为gcd(a,N)的倍数,否则,等式同除以gcd(a,N),则等式右边不为整数。
#故若b不是gcd(a,N)的倍数,则无解
#将上述等式化为a*x'+N*y'=gcd(a,N);则x=x'*(b/gcd(a,N))
def gcd(a,b):
if b==0:
return a
else:
return gcd(b,a%b)
def f(a,b,N):
if b%gcd(a,N)!=0:
print("NO SOLUTION!")
return 0
else:
r0,r1,s0,s1=1,0,0,1
while N:
q,a,N=a//N,N,a%N
r0,r1=r1,r0-q*r1
s0,s1=s1,s0-q*s1
return r0*(b/gcd(a,N))
#由上题可知,ax=(1 mod N)可写为:ax+yN=1。
#条件:a与N互质。
#否则,若a与N不互质,则必存在不为1的整数c为a与N的最大公约数。
#那么,提取c,移至等式右边,得1/c,不为整数,无解。故a与N需互质。
#由于a与N互质,则gcd(a,N)=1;故ax+yN=1=gcd(a,N),求x
def gcd(a,b):
if b==0:
return a
else:
return gcd(b,a%b)
def f(a,N):
if gcd(a,N)!=1:
print("NO SOLUTION!")
return 0
else:
r0,r1,s0,s1=1,0,0,1
while N:
q,a,N=a//N,N,a%N
r0,r1=r1,r0-q*r1
s0,s1=s1,s0-q*s1
return r0