一． 分解质因数

每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，把一个合数用质因数相乘的形式表示出来，叫做分解质因数。如30=2×3×5 。分解质因数只针对合数。求一个数的质因数，要从最小的质数除起，一直除到结果为质数为止。分解质因数的算式叫短除法，和除法的性质相似，还可以用来求多个数的公因式。

const int MAXN = 100010;
int prime[MAXN] = {0};
bool isprime[MAXN] = {0};
int id = 0;
void getPrime() //素数筛法 {
    for (int i = 2; i < MAXN; i++) {
        if (!isprime[i]) prime[id++] = i;
        for (int j = 0; j < id && i * prime[j] <= MAXN && i * prime[j] != 0; j++) isprime[i * prime[j]] = 1;
    }
}
void getPrimeFactor(int n) {
    getPrime();
    if (n < 2) return;
    if (!isprime[n]) cout << n;
    else {
        for (int i = 0; prime[i] < n; i++) {
            if (n % prime[i] == 0) {
                cout << prime[i] << " ";
                getPrimeFactor(n / prime[i]);
                break;
            }
        }
    }
}

二． 欧拉函数

对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目。根据定义可以写出

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
int getfi(int n) {
    int fi = 0;
    for (int i = 1; i < n; i++) if (gcd(i, n) == 1) fi++;
    return fi;
}

根据欧拉函数通式

1772640-20190903201415642-269699946.png

可以写出

int ksm(int a, int b) {
    int res = 1;
    for (; b; b >>= 1, a *= a) if (b & 1) res *= a;
    return res;
}
int getfi(int n) {
    int fi = 1;
    getPrime();
    if (n == 1 || !isprime[n]) return 1;
    for (int i = 0; prime[i] < n; i++) {
        if (n % prime[i] == 0) {
            int cnt = 0;
            while (n % prime[i] == 0) {
                cnt++;
                n /= prime[i];
            }
            fi *= (prime[i] - 1) * ksm(prime[i], cnt - 1);
        }
    }
    return fi;
}

欧拉函数通式可根据算数基本定理证明：

1772640-20190903201613706-566609640.png

三． 欧拉定理

欧拉定理描述：

1772640-20190903201701048-984673792.png

扩展欧拉定理：

1772640-20190903201613706-566609640.png

Super_log 题目链接: https://nanti.jisuanke.com/t/41299

题目大意是已知a，b，m，1≤a≤1000000，0≤b≤1000000，1≤m≤1000000，求

类似的，我们可以欧拉降幂

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ksm(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1, a = a * a % mod) if (b & 1) res = res * a % mod;
    return res;
}
ll getfi(ll x) {
    ll i, ans = x;
    for (i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            ans = ans / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    }
    if (x != 1) ans = ans / x * (x - 1);
    return ans;
}
ll solve(ll n, ll m, ll p) {
    if (p == 1) return 0;
    if (m == 0) return 1;
    ll fi = getfi(p);
    ll f = solve(n, m - 1, fi);
    if (f < fi && f) return ksm(n, f, p);
    else return ksm(n, f + fi, p);
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        ll a, b, m;
        cin >> a >> b >> m;
        ll ans = solve(a, b, m);
        cout << ans % m << endl;
    }
    return 0;
}

ps：欧拉公式：

跟上述无关，纯粹为了区分 e^{ix}=\cos x + i\sin x