快速幂

模板题:P1226 【模板】快速幂||取余运算 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

原理

$$ a^{n}=\left\{\begin{matrix} a^{n-1}\cdot a & n\space mod\space{2}=1 \\ a^{\frac{n}{2}}\cdot a^{\frac{n}{2}}& n\space mod\space2=0 \space and \space n\ne 0\\ 1&n=0 \end{matrix}\right. $$

$$ a^n = a^{{0\space or\space 1}\cdot 2^0}+a^{{0\space or\space 1}\cdot 2^1}+...+a^{{0\space or\space 1}\cdot 2^{\log_{2}{n}}} $$

其中的$0\space or\space 1$取决于$(n)_2$的第$k$位上是0还是1

代码

#include <iostream>
using namespace std;
long long a, b, p;
template <class T>
T EBS(T a, T b, const T p)
{
    T ans = 1 % p;
    a %= p;
    for (; b; b >>= 1)
    {
        if (b & 1) ans = 1ll * (ans * a) % p;
        a = 1ll * (a * a) % p;
    }
    return ans;
}
int main()
{
     cin >> a >> b >> p;
     printf("%d^%d mod %d=%d", a, b, p, EBS(a, b, p));
}