快速幂/快速乘模板

 1 ll quick_mod(ll a,int n)//求a的n次方
 2 {
 3     ll sum=1;//注意是乘法，所以初始化为1
 4     while(n)
 5     {
 6         if(n&1)//&运算符表示取这个数二进制的最后一位
 7         {
 8             sum=sum*a%mod;//若这位为1那么总和就应该乘当前的a
 9         }
10         a=a*a%mod;//不论该位为0还是1，a都应该平方一波，具体自己理解
11         n>>=1;//把n的二进制右移一位，等价于n/=2;
12     }
13     return sum;
14 }

1 ll mul(ll a, ll b, ll p){//快速乘，计算a*b%p 
2     ll ret = 0;
3     while(b){
4         if(b & 1) ret = (ret + a) % p;
5         a = (a + a) % p;
6         b >>= 1;
7     }
8     return ret;
9 }