最大公約数

最大公約数を求めるgcd関数

ユークリッド互除法によってaとbのgcdが求まる

計算量はO(log min(a,b) )らしい

long long gcf(long long a,long long b){

    if(!a|!b)return 0;

    do{

        if(a<b)swap(a,b);

        a%=b;

    }while(a);

    return b;

}

一行にするとこう

long long gcf(long long a,long long b){if(!a|!b)return 0;do{if(a<b)swap(a,b);a%=b;}while(a);return b;}

 

↑gcfってなんだ