题目描述

求 a 的 b 次方对 p 取模的值。

输入格式

三个整数 a,b,p,在同一行用空格隔开。

输出格式

输出一个整数，表示a^b mod p的值。

数据范围

$1≤a,b,p≤10^9$

输入样例：

3 2 7

输出样例：

2

题解：

按照朴素算法就是把a连乘b次，这样一来时间复杂度是O(b)也即是O(n)级别，快速幂能做到O(logn)。

$a^b$，那么其实b是可以拆成二进制的，该二进制数第i位的权为$2^{(i-1)}$，例如当b==11时，$a^{11}=a^{(2^0+2^1+2^3)}$ 。

11的二进制是1011，11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1，因此，我们将a¹¹转化为算 $a^(2^0)*a^(2^1)*a^(2^3) $ 。

由于是二进制，很自然地想到用位运算这个强大的工具： &  和 >> ，&运算通常用于二进制取位操作，例如一个数 & 1 的结果就是取二进制的最末位。还可以判断奇偶x&1==0为偶，x&1==1为奇。>>运算比较单纯,二进制去掉最后一位 。

代码：

#include<bits/stdc++.h>
using namespace std;

int a,b,mod;

int main(void)
{
    cin >> a >> b >> mod;

    int res = 1 % mod;

    while(b)
    {
        if(b&1) res = 1ll * res * a % mod;

        a = 1ll * a * a % mod;
        b >>= 1;
    }

    cout << res;
    return 0;
}