python/TangDou/AcWing/Math/FMXDL_3.cpp

#include <bits/stdc++.h>

using namespace std;

//计算2^100 %13的值
int fun1(int a, int p, int mod) {
    //前提p是质数,a不是p的倍数，有费马小定理
    int ans = pow(a, p % (mod - 1)); //利用费马小定理，降幂 p'= p % (mod - 1),然后再计算 pow(a,p'),这个就小多了
    ans %= mod;                      //再最后模一下mod就可以了
    return ans;
}

// fun2和fun3都会受到时间或者空间的限制，而fun1直接使用了费马小定理可以迅速的求取答案
int fun2(int a, int p, int mod) {
    int ans = pow(a, p); //不管p多大，我就是个算~暴力!但问题是你不怕爆掉int上界？不会溢出？
    ans %= mod;          //最后取模
    return ans;
}

int fun3(int a, int p, int mod) {
    int ans = 1;
    while (p--) { //既然怕爆int上界，那么就一步一取模，一步一计算。笨的要死，你不怕慢死啊：人家费马小定理只需要一步，你需要p步！而且,p还不小，慢的要死！
        ans *= a;
        ans %= mod;
    }
    ans %= mod;
    return ans;
}

int main() {
    for (int i = 1; i <= 100; i++) {
        cout << fun1(2, i, 13) << endl;
        cout << fun2(2, i, 13) << endl;
        cout << fun3(2, i, 13) << endl;
    }
    return 0;
}