1.快速幂（快速模幂） ①求a^b:
代码语言：javascript复制int pow(int a, int k) {
int ans = 1;
while(k) {
if(k &1) ans *= a; //判断奇偶只用判断最后一位比取模快
a *= a;
k >>=1; //比除法快多了
}
return ans;
}
②求a^b%p
int pow_mod(int a, int k,int mod) {
int ans = 1%mod;
while(k) {
if(k &1) ans =(long long) ans*a%mod; //防止在对P取模前溢出
a = (long long)a*a%mod;
k >>=1; //比除法快多了
}
return ans;
}
例题：BZOJ1008
2.快速乘法
方法①
long long quickMul(long long a,long long b,long long mod)
{
long long ans=0;
while(b){
if(b&1) ans=(ans a)%mod;
a=(a a)%mod; //（计算机加法比乘法快，a a比a*2快）
b>>=1;
}
return ans;
}
方法②：高效算法
long long quickMul(long long a,long long b,long long mod)
{
a%=mod;
b%=mod;
long long ans=0;
while(b){
if(b&1){
ans =a;
if(ans>=mod)
ans-=mod;
}
b>>=1;
a<<=1;
if(a>=mod) a-=mod;
}
return ans;
}
方法③：使用long double优化版
long long quickMul(long long a,long long b,long long mod)
{
a%=mod;
b%=mod;
long long c=(long double) a*b/mod;
long long ans=a*b-c*mod;
if(ans<0) ans =mod;
else if(ans>=mod) ans-=mod;
return ans
}
