『算法-ACM 竞赛-数学-数论』快速幂-最大公约数–位运算模板

ACM 常用模板合集

//位运算求解最大公约数
long long gcd(long long a,long long b)
{
 if(a<b)   return gcd(b,a);
 if(b==0) return a;
 if((a&1)==0&&(b&1)==0) return 2*gcd(a>>1,b>>1);//a and b are even
 if((a&1)==0) return  gcd(a>>1,b);   // only a is  even
 if((b&1)==0) return  gcd(a,b>>1);   // only b is  even
 return    gcd((a+b)>>1,(a-b)>>1);   // a and b are odd
}

inline ll ksm(ll x,ll k,ll mod){
    ll ans=1;
    for(;k;k>>=1,x=mul(x,x,mod))
    	if(k&1)ans=mul(ans,x,mod);
    return ans;
}