快速幂取模公式原理和C++实现

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

int ksm(int m, int n, int k) {
    if (m == 1 || n == 0) return 1 % k;
    if (n % 2 == 0)
        return ((ksm(m, n / 2, k) % k) * (ksm(m, n / 2, k) % k)) % k;
    else
        return ((ksm(m, n / 2, k) % k) * (ksm(m, n / 2, k) % k) * (m % k)) % k;
}

int main() {
    int a, b, c;
    cin >> a >> b >> c;  // a的b次幂模c的结果
    cout << ksm(a, b, c);

    return 0;
}