灰太狼648 2023-10-14 17:59 采纳率: 0%
浏览 14

关于#算法#的问题:输出二者的乘法逆元,注意不限定a和b的大小顺序(语言-python)


def gcd(m,b):
    if b == 0:
        return m
    else:
        return gcd(b, m%b)
def extendGcd(m,b):
    if b == 0:
        return 1, 0
    else:
        x, y = extendGcd(b, m%b)
        x, y = y, (x-(m//b)*y)
        return x, y
def main():
    a = int(input()) 
    b = int(input())
    c = gcd(a,b)
    if c!= 1:
        print("None")
    else: 
            t,r = extendGcd(a,b)
            print(r)
    
if __name__=='__main__':
    main()

题目要求:已知整数a、b`,设计扩展欧几里得算法,如果a和b不互素,输出None;如果a和b互素,输出二者的乘法逆元,注意不限定a和b的大小顺序。
但是测试集结果要求乘法逆元是正数,在a=550,b=1759的时候,求得逆元是-111为负数。请问怎么才能确保逆元是正数?

  • 写回答

3条回答 默认 最新

  • wang_nn 2023-10-14 18:16
    关注

    啥是乘法逆元啊?

    评论

报告相同问题?

问题事件

  • 创建了问题 10月14日