关于欧拉函数及其求法的复习。

这里是。

一句话总结：

\(a^b​\) \(mod​\) \(m​\) \(≡​\) \(a^b​\) \((b < phi(m))​\)

\(a^b\) \(mod\) \(m\) \(≡\) \(a^{b \% phi(m)+phi(m)}\) \((b >= phi(m))\)

实际上不需要记欧拉定理，后面这个在应用上已经可以涵盖前面的了。

用于优化指数非常大的情况。

#include 
    
     using namespace std;#define LL long longconst int N = 1000010;int tot, divv[N];int a, b, m;int fpow (int a, int b, int m) {    int res = 1;    while (b) {        if (b & 1) {            res = 1LL * res * a % m;        }        a = 1LL * a * a % m;        b >>= 1;    }    return res;}int main () {    cin >> a >> m;    int mx = sqrt (m), tmp = m;    for (int i = 2; i <= mx; ++i) {        if (tmp % i == 0) {            divv[++tot] = i;            while (tmp % i == 0) tmp /= i;        }    }    if (tmp != 1) divv[++tot] = tmp;    int _phi = m;    for (int i = 1; i <= tot; ++i) {        _phi = _phi / divv[i] * (divv[i] - 1);    }    int b = 0, ch = getchar (), type = 1;    while ('9' < ch || ch < '0') ch = getchar ();    while ('0' <= ch && ch <= '9') {        b = b * 10 + ch - '0';        if (b >= _phi) {            type = 2;            b = b % _phi;        }        ch = getchar ();    }    if (type == 2) b = b % _phi + _phi;    cout << fpow (a, b, m);}