AcWing 1297. 超级GCD

AcWing 1297. 超级GCD 原题链接中等

作者：

xhQYm , 2020-06-20 11:27:43 , 所有人可见 , 阅读 1130

其实就是GCD模板，只不过是高精

高精怎么办？除了手写高精当然还可以 __int128 和 Py 啦

Py代码：

a=int(input()) #输入a
b=int(input()) #输入b
while (b):
    a%=b 
    a,b=b,a # 交换
print(a) #输出

时间复杂度 $O(\log n)$ ，~~轻松水过~~

ZTEG 2020-06-20 16:50

__int128不行吧。。。

xhQYm 2020-06-21 20:39

谔？是acwing不支持吗

xhQYm 2020-06-21 20:39

哦好像精度不够而且慢。。py是分治乘

ZTEG 2020-06-21 20:57 回复了 xhQYm 的评论

人生苦短，我学python

Py实现高精STO学到了