<span>快速幂||取余运算</span>

题目描述

给你三个整数 b,p,k，求 \(b^p\) mod k。

输入格式

输入只有一行三个整数，分别代表 b,p,k。

输出格式

输出一行一个字符串 b^p mod k=s，其中b,p,k分别为题目给定的值，s为运算结果。

数据规模与约定

对于100%的数据，保证0 \(\leq\) b,p \(\leq\) \(2^{31}\)，1 \(\leq\) k \(\leq\) \(2^{31}\) 。

思路

快速幂的模板题，没有什么好说的。有两个细节需要注意:
1)a%2==1与a&1==1是等价的。
2)取模的运算不会干涉乘法运算。
3)根据费马小定理，如果k是一个质数，我们可以计算\(b^{p mod(k-1)}\)来加速算法过程。
代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int ll;
long long binpow(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll b,p,k;
    cin>>b>>p>>k;
    cout<<b<<"^"<<p<<" mod "<<k<<"="<<binpow(b%k,p,k)%k<<endl;
    return 0;
}

参考资料

1）https://oi-wiki.org/math/quick-pow/