最大公约数及求解x*a+y*b=1

#-*- coding:utf-8 -*- def gcd(x,y):     #保证x、y为整数     if type(x) is not int or type(y) is not int :         return 'x and y must be integer'     #保证x、y为正数     if x <= 0 or y <= 0:         return 'x and y must be positive number'     #将x、y按大到小排序,保证(x > y)     x,y = sorted((x,y),reverse=True)     A, B = x, y     rt = []     '''     x1 = a1 * x2 + x3    x3 = -a1 * x2 + x1   x3 = p1 * x2 + q1 * x1                                                 p1 = -a1  q1 = 1     x2 = a2 * x3 + x4    x4 = -a2 * x3 + x2   x4 = p2 * x2 + q2 * x1                                                 p2 = -a2*p1+1 q2 = -a2*q1     x3 = a3 * x4 + x5    x5 = -a3 * x4 + x3   x5 = -a3*(p2 * x2 + q2 * x1) + (p1 * x2 + q1 * x1)                                                 x5 = (-a3*p2 + p1)*x2 + (-a3*q2 + q1)*x1     ...     x = temp * y + z     x = y , y = z (z=x%y)                                              '''     #a1     temp = A/B     p1 = -temp      q1 = 1     rt.append('%4d = %4d*%-4d + %4d'%(A,temp,B,A%B))     #说明不互质,即有最大公约数,输出最大公约数     if A%B == 0:         rt.append('gcd(%d,%d)=%d'%(B,A,B))         return rt     #最大公约数为1,即互质,输出等式  1 = x*a+y*b     if A%B == 1:         rt.append(' 1 = %d*%d + %d*%d'%(p1,y,q1,x))         return rt          A, B = B, A%B     #a2     temp = A/B     p2 = -temp*p1+1     q2 = -temp*q1               while True:         rt.append('%4d = %4d*%-4d + %4d'%(A,A/B,B,A%B))         #print '%4d = %4d*%4d + %4d*%4d'%(A%B,p2,y,q2,x)         #print '*'*30         #同上         if A%B == 0:             rt.append('gcd(%d,%d)=%d'%(y,x,B))             return rt         if A%B == 1:             rt.append(' 1 = %d*%d + %d*%d'%(p2,y,q2,x))             return rt                      temp1 ,temp2 = p2,q2                  A, B = B, A%B         temp = A/B                  p2 = -temp*p2 + p1         q2 = -temp*q2 + q1         p1, q1 = temp1,temp2 if __name__ == '__main__':            rt = gcd(71,192)     for v in rt:         print v 运行结果  192 =    2*71   +   50   71 =    1*50   +   21   50 =    2*21   +    8   21 =    2*8    +    5    8 =    1*5    +    3    5 =    1*3    +    2    3 =    1*2    +    1  1 = -73*71 + 27*192

网址：最大公约数及求解x*a+y*b=1 https://www.yuejiaxmz.com/news/view/82196

相关内容

求y=log(1/2)^1/(x^2
若x²+y²＝4，求3x+4y的最大值
小贴士：已知x+y+xy=54，求x+y的值，老师的解法错在哪里？
x*y=k
隐函数求导x^y=y^x,求y'解:原式整理为:ylnx=xln 爱问知识人
【（x+y）（x的平方
定义符号min{a.b}的含义为:当a≥b时.min{a.b}=b,当a＜b时.min{a.b}=a．如:min{2.
y=x
y=f(x)是什么意思
直线y=kx+b与直线y=

随便看看