广义欧几里得除法求sa+tb=(a,b)

发表于 | 更新于: | 分类于 | 阅读次数: |
字数统计: 99 字 | 阅读时长 ≈ 1 分钟

信安数基

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

m=int(input('please input m:'))
m1=m
n=int(input('please input n:'))
n1=n
r = m % n
q=[]#从q1开始,到qn
yu=[r]
while(r!=0):
    m=n
    n=r
    r=m%n
    yu.append(r)
    q.append(m//n)

q.pop()
print('(m,n)='+str(yu[-2]))
s=[0,1]
t=[1,-1]

for i in range(len(q)):
    s.append(-q[i]*s[i+1]+s[i])
    
    t.append(-q[i]*t[i+1]+t[i])


s1=s.pop()
t1=t.pop()
print(str(s1)+'*'+str(m1)+'+'+str(t1)+'*'+str(n1)+'=1')