简单数论知识点

常用符号约定

d|n当n为常数，而d为变量时，表示枚举n的所有约数；反之，若d为常数n为变量，则表示枚举d的所有倍数(d,2d,3d...)。
[x]条件函数，当括号里的表达式为真时，函数值为1，否则为0
a \perp b表示a，b互质

最大公约数

两个数的最大公约数(greatest common divisor)表示为gcd(a, b)或者(a, b)，当且仅当(a, b)=1时，a和b互质。
求最大公约数的算法：gcd(a, b) = gcd(b, a%b)

int gcd(int a, int b) {
    return b==0? a:gcd(b, a%b);
}

还有一种求最大公约数的算法：更相减损术。gcd(a, b) = gcd(a, a-b)。这个算法使得大于2的所有的数的欧拉函数值都是偶数，因为和一个数互质的数总是成对出现的。
同时根据以上算法，我们还能得出与n互质的数的总和为n*\frac{Φ(n)}{2}。因为共有\frac{Φ(n)}{2}对质数，每对和为n。
欧拉函数还有一大性质，欧拉反演
我们定义一个函数f(n) = \sum_{d|n} Φ(d)。即n的所有约数的欧拉函数之和。这个函数满足以下性质：

f(n)是积性函数。f(mn)=f(m)f(n)
f(p^k) = Φ(1) + Φ(p) + Φ(p^2) + ··· + Φ(p^k) = 1 + (p-1) + (p^2-p) + ··· + (p^k-p^{k-1}) = p^k
f(n) = f(\prod p_i^{q_i}) = \prod f(p_i^{q_i}) = \prod p_i^{q_i} = n。

欧拉函数

设n是自然数，数列1,2,...,n中与n互素的数的个数称为n的Euler函数，记作Φ(n)。
计算公式：Φ(n) = n (1-\frac{1}{p1}) (1-\frac{1}{p2})···(1-\frac{1}{p3})

pi为n的互不不相等的素因子。
性质

若p是素数，则Φ(p)= p-1。
设p和q是素数，对n=pq，有 Φ(n)= Φ(p) Φ(q)= (p-1)(q-1)

欧拉定理

对任意整数a和n互素，则a^{Φ(n)}=1 (mod n)
特殊的，当n为素数时，有费马小定理：a^{n-1}=1 (mod n)
欧拉定理适用于幂为负数的情况。
若a和n互素，则有a^{-1} \equiv a^{Φ(n)-1}modn。
当n为质数时，a关于n的逆元为a^{-1} \equiv a^{n-1-1}modn

扩展欧拉定理

扩展欧拉定理是由欧拉定理推得的。扩展欧拉定理不适用于求幂为负数的情况。

a, n互素，即(a,n)=1时，a^b ≡ a^{b\%Φ(n)}modn这是不用质疑的，欧拉定理。
a, n不互素时，若b<Φ(n)，那么a^b ≡ a^{b}modn，这时候b的值应该不会太大，也容易计算。
a, n不互素时，若b>=Φ(n)，那么a^b ≡ a^{b\%Φ(n)+Φ(n)}modn，b也不会太大，也好计算。

同余方程

求方程ax \equiv 1(modb)的最小正整数解。
把方程表示成ax + by = 1的形式，根据裴属定理，若(a,b)!=1，则方程无解。利用扩展欧几里得求得一组解后，其余解可由该解推出：x = x_0 + bt, y = y_0 + at。

同余方程

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
void extgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1, y = 0;
        return;
    }

    extgcd(b, a % b, y, x);
    y -= a / b * x;
    return;
}

int main() {
    ll a, b, x, y;
    cin >> a >> b;
    extgcd(a, b, x, y);
    cout << (x % b + b) % b << endl;
    return 0;
}