二进制GCD算法解析

UPD 2018.3.30 这个好像就是更相减损术的样子emmm

UPD 2018.5.22 好像不是更相减损术而是叫Stein算法的样子emmm

 

蒟蒻来做个二进制GCD笔记。

为什么要写这个东西呢，因为按照ysy神犇在这次luogu夏令营的说法，常数会小很多。

我再查了一下（ysy神犇没说实现啊orz），这玩意的原理说起来大概是这样的：

因为普通的辗转相除法求gcd需要用到取模，所以常数比较慢。

我们使用另一种算法：

求gcd(a,b)。有三种情况：

　　1.a,b为偶数，则gcd(a,b)=2*gcd(a/2,b/2)

　　2.a为奇数，b为偶数，则gcd(a,b)=gcd(a,b/2)

　　3.a,b为奇数。假设a>=b，则gcd(a,b)=gcd((a-b)/2,b)

　　4.a为0，则返回b

然后以上的除法和判奇偶性可以使用位运算处理。

取较大值可以使用内联函数降低常数。

然后....emmm

下面是两种算法的执行时间。原题：BZOJ 入门P1234

 

可能是范围开的不够大？（一脸懵逼）

然后我自己测了一组比较大的数据。

9223372036854775800 529215046068469760

每个程序运行5次，忽略误差较大的运行，取平均值，得到的数据如下：

普通gcd算法：13.576ms

二进制gcd算法：13.044ms

总之...emm，掌握还是很简单的。

至于什么时候用...各位见仁见智吧。

代码如下：

#include<iostream>
using namespace std;
typedef long long ll;
inline ll abs(ll x){
    return x<0?-x:x;
}
inline ll min(ll a,ll b){
    return a<b?a:b;
}
inline ll gcd(ll a,ll b){
    if(a==0)return b;
    if(b==0)return a;
    if(!(a&1)&&!(b&1))return 2*gcd(a>>1,b>>1);
    else if(!(a&1))return gcd(a>>1,b);
    else if(!(b&1))return gcd(a,b>>1);
    else return gcd(abs(a-b),min(a,b));
}
 
int main(){
    ll a,b;
    cin>>a>>b;
    cout<<"gcd="<<gcd(a,b);
    return 0;
}