信息学奥赛一本通T1616-A 的 B 次方（C++代码）

解法一：

最朴素的方法，直接循环b次，求出a^b的结果，最后对c取模

#include using namespace std;
int main() {
    int a,b,c,ans = 1;
    cin >> a >> b >> c;
    for(int i = 1;i <= b;i++) {
        ans *= a;
    }
    cout << (ans % c) << endl;
    return 0;
}

但是这么写有问题，如果b的值太大，会导致溢出和超时（指数爆炸），这里的复杂度是O(n)

解法二：快速幂

a^b mod m 这个式子中，最容易导致超时的部分是a^b，我们可以先思考一下这部分怎么算才快

假设，在草稿计算3¹⁰，我们可以分解成3¹⁰ = (3²)⁵ = 9⁵ = 9 * 9⁴ = 9 * (81)² = 9 * (81¹)²

可以发现一些规律：当指数为偶数的时候，将指数除以2，底数平方；当指数为奇数的时候，提取出一次方的底数，再将指数除以2，底数平方

这时候就可以设三个变量，设base为底数，设index为指数，设mod取模数，有了变量和规律，代码就不难了

另外，这里也要考虑数据范围问题，根据题目给出的范围，可能会造成指数爆炸，所以使用C++中long long来存储数据

这个的复杂度是O(log₂n)

typedef long long ll;
#include using namespace std;
ll fast_pwoer(ll base,ll index,ll mod) {
    ll ans = 1;
    base %= mod;
    //指数为循环次数
    while (index) { 
    //判断奇偶性
        if (index % 2 == 1) {
            ans = (ans * base) % mod;
        }
        base = (base * base) % mod;
        index /= 2;
    }
    return ans;
}
int main() {
    int a,b,c;
    cin >> a >> b >> c;
    cout << (fast_pwoer(a,b,c)) << endl;
    return 0;
}