【模板】快速幂||取余运算

链接

快速求$a^b$

1. 如果将a自乘一次，就会变成$a^2$。再把$a^2$自乘一次就会变成$a^4$，然后是$a^8$……自乘n次的结果是$a^{2^n}$

2. $a^x$$a^y$=$a^{x+y}$

   int quickPower(int a, int b)//是求a的b次方
   {
      int ans = 1, base = a;//ans为答案，base为a^(2^n)
      while(b > 0)//b是一个变化的二进制数，如果还没有用完
      {
          if(b & 1)//&是位运算，b&1表示b在二进制下最后一位是不是1，如果是：
              ans *= base;//把ans乘上对应的a^(2^n)
   
          base *= base;//base自乘，由a^(2^n)变成a^(2^(n+1))
          b >>= 1;//位运算，b右移一位，如101变成10（把最右边的1移掉了），10010变成1001。现在b在二进制下最后一位是刚刚的倒数第二位。结合上面b & 1食用更佳
      }
      return ans;
   }

3. 取余运算

(A + B) mod b = (A mod b + B mod b) mod b
(A × B) mod b = ((A mod b) × (B mod b)) mod b

while(b > 0)
    {
        if(b & 1)
        {
            ans *= base;
            ans %= m;
            /*ans=(ans*base)%K*/
        }
        base *= base;
        base %= m;
        b >>= 1;
    }

能保证这样下来最后的结果与“先乘到最后，再取余”的结果一样。

#include<cstdio>
#include<iostream>
using namespace std;
long long a,b,k;
long long ksm(long long a,long long b){
    long long base=a,ans=1;
    while(b>0){
        if(b&1){
            ans*=base;
            ans%=k;
        }
        base*=base;
        base%=k;
        b>>=1;
    }
    return ans%k;
}
int main(){
    cin>>a>>b>>k;
    cout<<a<<"^"<<b<<" mod "<<k<<"="<<ksm(a,b);
    return 0;
}