欧拉函数、快速幂、扩展欧几里得、中国剩余定理

欧拉函数： $1\sim n$ 中与 $n$ 互质的数的个数。如与 6 互质的有 1 和 5，$\Phi(6)=2$ 。若 $p$ 是质数，则 $\Phi(p) = p-1$ 。

$$\Phi(n)=n*\frac{p_1-1}{p_1}\frac{p_2-1}{p_2}*...*\frac{p_k-1}{p_k}$$

// 公式法
#include <iostream>
using namespace std;
int main(){
    int k; cin >> k;
    while(k --){
        int n; cin >> n;
        int res = n;
        for(int i = 2; i <= n / i; i ++){
            if(n % i == 0){
                res = res / i * (i - 1); // 先除再乘避免溢出
                while(n % i == 0) n /= i;
            }
        }
        if(n > 1) res = res / n * (n - 1);
        cout << res;
    } 
}

// 筛法求欧拉函数
typedef long long ll;
const int N = 1000010
int primes[N], st[N], cnt;
int phi[N];
ll get_eulers(int n){
    phi[1] = 1;
    for(int i = 2; i <= n; i ++){
        if(!st[i]) {
            primes[cnt ++] = i;
            phi[i] = i - 1;
        }
        for(int j = 0; primes[j] <= n / i; j ++){
            st[primes[j] * i] = 1;
            if(i % primes[j] == 0) {
                phi[primes[j] * i] = primes[j] * phi[i];
                break;
            }
            // else if(i % primes[j] != 0)
            phi[primes[j] * i] = (primes[j] - 1) * phi[i];
        }
    }
    ll res = 0;
    for(int i = 1; i <= n; i ++) res += phi[i];
    return res;
}

欧拉定理： 若 $a$ 与 $n$ 互质，则 $a^{\Phi(n)}\equiv1(\mod n)$ 。

快速幂：

#include <iostream>
using namespace std;
using ll = long long;
int qmi(int a, int k, int p){
    int res = 1;
    while(k){
        if(k & 1) res = (ll)res * a % p;
        k >>= 1;
        a = (ll)a * a % p;
    }
    return res;
}
int main(){
    int n; cin >> n;
    while(n --){
        int a, k, p;
        cin >> a >> k >> p;
        cout << qmi(a, k, p) << endl;
    }
}

逆元：$b,m$ 互质，$b$ 整除 $a$，若 $\frac{a}{b}\equiv a\cdot x(\mod m)$ ，$x$ 称为 $b$ 的逆元。求逆元即求 $b*x\equiv 1(\mod m)$ 的解。

// 求一般逆元
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll exgcd(long long a, long long b, ll & x, ll & y){
    if(b == 0){
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main(){
    int n;
    scanf("%d", &n);
    while (n -- ){
        ll a, p, x, y;
        cin >> a >> p;
        ll d = exgcd(a, p, x, y);
        if (d != 1) puts("impossible");
        else cout << (x % p + p) % p << endl;
    }
    return 0;
}

// 求逆元
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int qmi(int a, int b, int p){
    int res = 1;
    while (b){
        if (b & 1) res = (ll)res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

int main(){
    int n;
    scanf("%d", &n);
    while (n -- ){
        int a, p;
        scanf("%d%d", &a, &p);
        if (a % p == 0) puts("impossible");
        else printf("%lld\n", qmi(a, p - 2, p));
    }

    return 0;
}

扩展欧几里得：

int exgcd(int a, int b, int &x, int &y){
    // ax + by = (a, b)
    if(b == 0) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y); // bx + (a % b)y = (a, b)
    int z = x;
    x = y;
    y = z - a / b * y;
    return d; 
}
int exgcd(int a, int b, int &x, int &y){
    // ax + by = (a, b)
    if(b == 0) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x); // by + (a % b)x = (a, b)
    y -= a / b * x;
    return d; 
}

中国剩余定理：

表达整数的奇怪方式：

先考虑两个方程：

$$x\equiv m_1(\mod a_1)\\ x\equiv m_2(\mod a_2)$$

若有解，则存在 $k_1, k_2$ ，$x=m_1+k_1a_1=m_2+k_2a_2$，整理得

$$k_1a_1-k_2a_2=m_2-m_1\tag{1}$$

上式是关于 $k_1,k_2$ 的方程，由裴蜀定理知方程有解的充要条件是 $(a_1,a_2) | m_2-m_1$ ，若有解，则：

$$k_1+k\frac{a_2}{d},k_2+k\frac{a_1}{d}\quad\text{都是(1)的解}，于是\\ x=(k_1+k\frac{a_2}{d})a_1 + m_1=a_1k_1+m_1+k\frac{a_1a_2}{d}=a_1k_1+m_1+k[a_1,a_2]$$

$x$ 即两个方程的全部解，如此两个方程即合并为一个方程，形式为 $x=x_0+ka$。再接着合并剩下的方程即可，$n$ 个方程共合并 $n-1$ 次。

#include <iostream>
using namespace std;
using ll = long long;
ll exgcd(ll a, ll b, ll& x, ll& y){
    if(b == 0){
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int main(){
    int n; cin >> n;
    bool has_answer = true;
    ll a1, m1; cin >> a1 >> m1;
    for(int i = 1; i < n; i ++){
        ll a2, m2; cin >> a2 >> m2;
        // 合并方程，求 k1, k2
        ll k1, k2; 
        ll d = exgcd(a1, a2, k1, k2);
        if((m2 - m1) % d != 0) {
            has_answer = false;
            break;
        }
        k1 = k1 * (m2 - m1) / d, k2 = k2 * (m2 - m1) / d;
        ll mod = a2 / d; // mod 要把 k1 模到比较小的范围
        k1 = (k1 % mod + mod) % mod;
        m1 = a1 * k1 + m1; // 更新 x0
        a1 = abs(a1 / d * a2); // 更新最小公倍数
    }
    if(has_answer) cout << (m1 % a1 + a1) % a1 << endl;
    else cout << "-1";
}

Q.E.D.