题目:
分析:
以为辗转相减会TLE呢……但是好像没这个数据……就这么水过去了……
辗转相减求a,b的gcd其实可以优化的:
1、若a为偶数,b为奇数:gcd(a,b)=gcd(a/2,b)
2、若a为奇数,b为偶数:gcd(a,b)=gcd(a,b/2)
3、若a,b都是偶数:gcd(a,b)=2*gcd(a/2,b/2)
3、若a,b都是奇数:gcd(a,b)=gcd(a-b,b) (a>b)
然后就涉及到高精度乘单精度,高精度减高精度,高精度除单精度……
本文共 283 字,大约阅读时间需要 1 分钟。
题目:
分析:
以为辗转相减会TLE呢……但是好像没这个数据……就这么水过去了……
辗转相减求a,b的gcd其实可以优化的:
1、若a为偶数,b为奇数:gcd(a,b)=gcd(a/2,b)
2、若a为奇数,b为偶数:gcd(a,b)=gcd(a,b/2)
3、若a,b都是偶数:gcd(a,b)=2*gcd(a/2,b/2)
3、若a,b都是奇数:gcd(a,b)=gcd(a-b,b) (a>b)
然后就涉及到高精度乘单精度,高精度减高精度,高精度除单精度……
转载于:https://www.cnblogs.com/wmrv587/p/4141503.html