第一问答网»论坛 › 中问网 › 问答 › 求教最大公约数10^1000以内的PASCAL算法

求教最大公约数10^1000以内的PASCAL算法

[复制链接]

11 |

3 | 2011-8-4 21:06:33 | 显示全部楼层 |阅读模式

最后是程序
难道不会超时吗？（最好贴代码）

使用道具举报

千问 | 2011-8-4 21:06:33 | 显示全部楼层

求最大公约数，自然想到用辗转相除法。但是高精度取模不是很好写，于是转用二进制法求最大公约数。gcd(a,b)=a
a=b
2×gcd(a/2,b/2)
a,b均为偶数
gcd(a/2,b)
a为偶数，b为奇数
gcd(a,b/2)
b为偶数，a为奇数
gcd(b,a-b)
a,b均为奇数且a>b
gcd(a,b-a)
...

使用道具举报