当前位置:网站首页>P2152 [SDOI2009]SuperGCD(模拟)

P2152 [SDOI2009]SuperGCD(模拟)

2021-08-10 08:43:43 wx6110fa547fd20

P2152 [SDOI2009]SuperGCD(模拟)

高精度下求两数的 g c d gcd gcd

人生苦短,我用python。

if __name__ == '__main__':
    import math
    print(math.gcd(int(input()),int(input())))

      
  • 1.
  • 2.
  • 3.

也可以用辗转相减法进行模拟。

优化一下:

g c d ( a , b ) gcd(a,b) gcd(a,b)

a , b a,b a,b都为偶数,则 g = 2 × g c d ( a 2 , b 2 ) g=2\times gcd(\dfrac{a}{2},\dfrac{b}{2}) g=2×gcd(2a,2b)

若只有一个偶数,则 g = g c d ( a 2 , b ) g=gcd(\dfrac{a}{2},b) g=gcd(2a,b) g c d ( a , b 2 ) gcd(a,\dfrac{b}{2}) gcd(a,2b)

否则 g = g c d ( b , a − b ) g=gcd(b,a-b) g=gcd(b,ab)

然后就是高精度乘低精, 高精除低精,高精减高精。注意不要用递归,用循环。

代码不上,太菜了,没写。

版权声明
本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_15326986/3328392

随机推荐