欧拉函数:
1.欧拉函数𝜑(𝑛)是定义在正整数n上的函数，表示小于或等于n的正整数中与n互质的数的个数
𝜑(𝑛)=n(1-1/p1)(1-1/p2)…(1-1/pk),(p为n的质因数); 由容斥定理推导,可由分解质因数求得n的质因数。

2.筛法求欧拉函数：给定一个正整数n，求 1∼n中每个数的欧拉函数之和。
线性筛法 + 对i是否与prime[j]互质讨论 
(1) 若i为质数 𝜑(i)=i-1;
(2) 若(i % prime[j] == 0) 𝜑(i * prime[j]) = prime[j] * 𝜑(i);
(3) 若(i % prime[j] != 0) 𝜑(i * prime[j]) = (prime[j]-1) * 𝜑(i);

快速幂：
1.快速幂：快速求𝑎^𝑏%p的问题,时间复杂度:O(logb),若对于n组数据,那么
时间复杂度为O(n∗logb) a^2^0 -> a^2^1 ->…-> a^2^logb

2.快速幂求逆元: 当n为质数时，可以用快速幂求逆元：a / b ≡ a * x (mod n)
两边同乘b可得 a ≡ a * b * x (mod n)即 1 ≡ b * x (mod n)
同 b * x ≡ 1 (mod n)由费马小定理可知，当n为质数时b ^ (n - 1) ≡ 1 (mod n)
拆一个b出来可得 b * b ^ (n - 2) ≡ 1 (mod n)故当n为质数时，
b的乘法逆元 x = b ^ (n - 2).

**欧拉定理：(若a与n互质) [ a^𝜑(n) ≡ 1 (mod n) ]** -> 
**费马小定理：当n为质数时b ^ (n - 1) ≡ 1 (mod n)**

扩展欧几里得算法：
给定n对正整数 ai,bi，对于每对数，求出一组 xi,yi，使其满足 ai×xi+bi×yi=gcd(ai,bi)

设ax1+by1=gcd(a,b), bx2+(a%b)y2=gcd(b,a%b);
由gcd(a,b)=gcd(b,a%b),可得:ax1+by1=bx2+(a%b)y2;
即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b) * by2;
即:ax1+by1=ay2 + b(x2-(a/b)*y2)

`LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}`

中国剩余定理：
难搞

给定 2n个整数 a1,a2,…,an和 m1,m2,…,mn，求一个最小的非负整数 x，满足 ∀i∈[1,n],x≡mi(mod ai)。

例子：
X  %  3 = 2
X  %  5 = 3  利用 扩展欧几里得定理 计算
X  %  7 = 2

Y1 = 5×7×[(5×7)−1]3 并且[(5×7)−1]3 = 2
Y2 = 3×7×[(3×7)−1]5 并且[(3×7)−1]5 = 1
Y3 = 3×5×[(3×5)−1]7 并且[(3×5)−1]7 = 1

https://www.acwing.com/solution/content/8552/