快速幂

C++ 代码

#include<iostream>
#include<cstdio>
using namespace std;

long long p;

long long fpow(long long a, long long b) {  //快速幂模板
    if(b == 0) return 1 % p;                //边界情况处理
    if(b == 1)  return a % p;    
    long long ans = 1;
    if(b % 2 == 0) {                        //如果b为偶数 a^b = a^(b/2) * a^(b/2)
        ans = fpow(a, b /2) % p;
        ans = (ans * ans) % p;
    } else {                                //如果b为奇数 a^b = a^(b/2) * a^(b/2) * a
        b--;
        ans = fpow(a, b /2) % p;
        ans = (ans * ans) % p;
        ans = (ans * a) % p;
    }
    return ans % p;    
}

int read() {            //快读模板
    int x = 0 , ch = getchar() , v = 1;
    while(!isdigit(ch)) {
        if(ch == '-')
            v = -1;
        ch = getchar();
    }
    while(isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();       
    }
    return x * v;
}

int main() {
    long long a, b;
    a = read();
    b = read();
    p = read();

    cout << fpow(a, b);
    return 0;
}