数学--数论--快速幂--最大公约数--位运算模板

//位运算求解最大公约数
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;
}