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<?-x:x;

}

inline ll min(ll a,ll b){

    return a<b?a:b;

}

inline ll gcd(ll a,ll b){

    if(a==)return b;

    if(b==)return a;

    if(!(a&)&&!(b&))return *gcd(a>>,b>>);

    else if(!(a&))return gcd(a>>,b);

    else if(!(b&))return gcd(a,b>>);

    else return gcd(abs(a-b),min(a,b));

}

int main(){

    ll a,b;

    cin>>a>>b;

    cout<<"gcd="<<gcd(a,b);

    return ;

}