[数论第二节]欧拉函数/快速幂/扩展欧几里得算法-五八三

欧拉函数
- 欧拉函数 $φ (N)$ : 1-N中与N互质的数的个数
- 若 $N = p_{1}^{a_{1}} \cdot p_{2}^{a_{2}} \cdot p_{3}^{a_{3}} \cdot \cdot \cdot \cdot p_{n}^{a_{n}}$ 其中p为N的所有质因子
- 则 $φ (N) = N (1 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) \cdot \cdot \cdot (1 - \frac{1}{p_{n}})$
- 证明：
  - 互质：两数的公共因子只有1
  - 去掉所有与N有(大于1的)公共因子的数，剩下的数就是与N互质的数
  - 对N的所有质因子 $p_{k}$ ，去掉所有 $\underset{―}{质数 p_{k} 的倍数}$ (与N有公共因子的数)， $\underset{―}{每个质数的倍数}$ 个数为 $\frac{N}{p_{k}}$ ，即 $N - \frac{N}{p_{1}} - \frac{N}{p_{2}} - \cdot \cdot \cdot - \frac{N}{p_{n}}$
  - 对于数 $p_{i} \cdot p_{j}$ ，在去掉 $p_{i}$ 的倍数和去掉 $p_{j}$ 的倍数的过程中去除了两次，所以要加上一次，即 $N - (\frac{N}{p_{1}} + \frac{N}{p_{2}} + \cdot \cdot \cdot + \frac{N}{p_{n}}) + (\frac{N}{p_{1} p_{2}} + \frac{N}{p_{1} p_{3}} + \cdot \cdot \cdot + \frac{N}{p_{n - 1} p_{n}})$
  - 对于数 $p_{i} \cdot p_{j} \cdot p_{k}$ ，在去掉 $p_{k}$ 的倍数的过程中被去掉了三次，在加上合数 $p_{i} \cdot p_{j}$ 的过程中被加上了三次，所以合数 $p_{i} \cdot p_{j} \cdot p_{k}$ 没有被去掉，因此要去掉它，即 $N - (\frac{N}{p_{1}} - \frac{N}{p_{2}} - \cdot \cdot \cdot - \frac{N}{p_{n}}) + (\frac{N}{p_{1} p_{2}} + \frac{N}{p_{1} p_{3}} + \cdot \cdot \cdot + \frac{N}{p_{n - 1} p_{n}}) - (\frac{N}{p_{1} p_{2} p_{3}} + \frac{N}{p_{1} p_{2} p_{4}} + \cdot \cdot \cdot + \frac{N}{p_{n - 2} p_{n - 1} p_{n}})$
  - 对于合数 $p_{i} \cdot p_{j} \cdot p_{k} \cdot p_{m}$ 同理，归纳递推可知，所有质数个数为： $N - \sum_{i = 1}^{n} \frac{N}{p_{i}} + \sum_{1 <= i < j <= n} \frac{N}{p_{i} p_{j}} - \sum_{1 <= i < j < k <= n} \frac{N}{p_{i} p_{j} p_{k}} + \cdot \cdot \cdot + (- 1)^{2 n - 1} \sum_{1 <= i < j < k < \cdot \cdot \cdot <= n} \frac{N}{p_{i} p_{j} p_{k} \cdot \cdot \cdot p}$
  - 同样基于容斥原理：
    - $| A \cup B \cup C | = | A | + | B | + | C | - | A \cap B | - | A \cap C | - | B \cap C | + | A \cap B \cap C |$
    - $| \cup_{i = 1}^{n} A_{i} | = \sum_{i} | A_{i} | - \sum_{i, j} | A_{i} \cap A_{j} | + \dots + (- 1)^{n + 1} | \cap_{i = 1}^{n} A_{i} |$
    - 与N有(大于1的)公共因子的个数 =| $p_{i}$ 的倍数的个数| – | $p_{i} p_{j}$ 的倍数的个数| + | $p_{i} p_{j} p_{k}$ 的倍数的个数 ··· $(- 1)^{n + 1}$ | $p_{i} p_{j} \cdot \cdot \cdot p_{n}$ 的倍数的个数|
  - 将上式因式分解后： $N (1 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) \cdot \cdot \cdot (1 - \frac{1}{p_{n}})$
- 容斥原理：
```
int res = a;
for(int i = 2; i <= a / i; ++ i){
    if(a % i == 0){//i为质因子
        res = res / i * (i - 1);//套公式
        while(a % i == 0) a /= i;//把因子除干净
    }
}
if(a > 1) res = res / a * (a - 1);//最后一个因子可能大于sqrt(a)
```
- 筛选法：
  - 利用线性筛选质数的过程求出每个数的欧拉函数
  - 欧拉函数为积性函数，当a与b互质时有 $φ (a \cdot b) = φ (a) \cdot φ (b)$
  - 当i为质数时， $φ (i) = i - 1$
  - 当 $\frac{i}{p_{j}} = 0$ 时， $p_{j}$ 为i的质因子，此时 $p_{j} \cdot i$ 的质因子与i的质因子完全相同，所以 $φ (p j \cdot i) = p j \cdot i \cdot (1 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) \cdot \cdot \cdot (1 - \frac{1}{p_{n}}) = p_{j} \cdot φ (i)$
  - 当 $\frac{i}{p_{j}} \neq 0$ 时， $p_{j}$ 不为i的质因子，此时 $p_{j} \cdot i$ 的质因子比i的质因子多一个 $p_{j}$ ，所以 $φ (p j \cdot i) = p j \cdot i \cdot (1 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) \cdot \cdot \cdot (1 - \frac{1}{p_{n}}) (1 - \frac{1}{p_{j}}) = p_{j} \cdot φ (i) \cdot (1 - \frac{1}{p_{j}}) = (p_{j} - 1) \cdot φ (i)$
  - 代码：
```
const int N = 1e6 + 10;
typedef long long LL;
int primes[N], cnt;//质数数组，下标
int st[N];//标记为合数
int phi[N];//欧拉函数
int 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;//质数i的欧拉函数为i - 1
        }
        for(int j = 1; primes[j] <= n / i; ++ j){
            int pj = primes[j];
            st[pj * i] = 1;
            if(i % pj == 0){//i是合数
                phi[pj * i] = pj * phi[i];//pj为i的质因子
                break;
            }
            else phi[pj * i] = (pj - 1) * phi[i];//pj不是i的因子
        }
    }
    
    LL ans = 0;
    for(int i = 1; i <= n; ++ i) ans += phi[i];
    return ans;
}
```
- 欧拉函数的应用
  - 欧拉定理
    - 若a与n互质，则 $a^{φ (n)} (\mod n) \equiv 1$
    - 证明：
      - 若a与b互质，且 $a (\mod b) \neq 0$ 则 $a (\mod b)$ 也与b互质
      - 设 $a_{1}, a_{2}, a_{3} \cdot \cdot \cdot a_{φ (n)}$ 为1~n中的所有与n互质的数
      - 每个数同时乘上a得 $a \cdot a_{1}, a \cdot a_{2}, a \cdot a_{3} \cdot \cdot \cdot a \cdot a_{φ (n)}$ 由于a也与n互质，所以乘a后所得的数也全部与n互质
      - 将每个数mod n，取模后的每个数都在1~n范围内，并且仍然都与n互质，显然取模后的这几个数就是原来的几个数，只不过数的顺序可能发生了变化
      - 将所有数相乘，则有 $a \cdot a_{1} \cdot a \cdot a_{2} \cdot a \cdot a_{3} \cdot \cdot \cdot a \cdot a_{φ (n)} (\mod n) = a_{1} \cdot a_{2} \cdot a_{3} \cdot \cdot \cdot a_{φ (n)}$
      - 所以有： $a^{φ (n)} \cdot (a_{1} a_{2} a_{3} \cdot \cdot \cdot a_{φ (n)}) (\mod n) \equiv (a_{1} \cdot a_{2} \cdot a_{3} \cdot \cdot \cdot a_{φ (n)})$ 即 $a^{φ (n)} (\mod n) \equiv 1$
      - 特别地，当n为质数时， $a^{n - 1} (\mod n) \equiv 1$ 为费马定理
快速幂
- 快速地求出 $a^{k} (\mod b)$ ，时间复杂度为 $O (l o g (k))$
- 将k拆分为二进制相加，即
- $k = c_{1} \cdot 2^{1} + c_{2} \cdot 2^{2} + c_{3} \cdot 2^{3} + \cdot \cdot \cdot + c_{n} \cdot 2^{n}$
- 其中 $c_{i}$ 是k的二进制的每一位(0/1)，n最大为k的二进制的位数
- 所以
- $a^{k} (\mod b) = a^{c_{1} \cdot 2^{1} + c_{2} \cdot 2^{2} + c_{3} \cdot 2^{3} + \cdot \cdot \cdot + c_{n} \cdot 2^{n}} (\mod b) = a^{c_{1} \cdot 2^{1}} \cdot a^{c_{2} \cdot 2^{2}} \cdot a^{c_{3} \cdot 2^{3}} \cdot \cdot \cdot a^{c_{n} \cdot 2^{n}} (\mod b)$
- 所以每次遍历k的所有二进制位，同时预处理出 $a^{i}$ ，根据k的二进制的取值将答案累乘
- 代码：
```
typedef long long LL;
//求a^k mod b
int qmi(int a, int k, int b){
	int res = 1;
	while(k){
		if(k & 1) res = (LL)res * a % b;//k的当前位非0，则将a累乘到答案
		k >>= 1;//k右移一位
		a = (LL)a * a % b;//a的幂倍增
	}
	return res;
}
```
- 快速幂求逆元
  - 若b与p互质，且 $b | a$ ， $\frac{a}{b} = a \cdot x (\mod p)$ ，则x为b的逆元
  - 两边乘b有 $a = a \cdot b \cdot x (\mod p)$
  - 所以有 $b \cdot x = 1 (\mod p)$
  - 若p是质数，有费马定理 $b^{p - 1} = 1 (\mod p)$ 则 $x = b^{p - 2}$
  - 若p不是质数，有欧拉定理 $b^{φ (p)} = 1 (\mod p)$ 则 $x = b^{φ (p) - 1}$
  - 代码：
```
int qmi(int a, int b, int p){
	略...
}
if(b与q互质){ //互质是有解的前提
	if(p为质数) cout << qmi(b, p - 2, p);
	else cout << qmi(b, phi[p] - 1, p);
}else 无解
```
扩展欧几里得定理
- 裴蜀定理：对于任意正整数a,b, 都一定存在整数x,y, 使得 $a x + b y = g c d (a, b)$ , 并且 $g c d (a, b)$ 一定是a与b能构造出来的最小公约数
- 扩展欧几里得算法就是求这样的x，y
- 用于求解方程 $a x + b y = g c d (a, b)$ 的解
- 当 $b = 0$ 时 $a x + b y = a$ 故而 $x = 1, y = 0$
- 当 $b \neq 0$ 时,因为
- $g c d (a, b) = g c d (b, a % b)$
- 而
- $b \cdot x_{1} + (a % b) \cdot y_{1} = g c d (b, a % b)$
- $b \cdot x_{1} + (a - ⌊ a / b ⌋ \cdot b) \cdot y_{1} = g c d (b, a % b)$
- $a y_{1} + b \cdot (x_{1} - ⌊ a / b ⌋) = g c d (b, a % b) = g c d (a, b)$
- 故而 $x = y_{1}, y = x_{1} - ⌊ a / b ⌋ \cdot y_{1}$
- 代码：
```
int exgcd(int a, int b, int &x, int &y){
    if(!b){ //b = 0时，ax + by = gcd(a, 0) = a,所以x = 1, y = 0;
        x = 1, y = 0;
        return a;
    }else {
        int d = exgcd(b, a % b, x, y);//交换a与b，x与y
        int t = x;
        x = y;//x1 = y2
        y = t - a / b * y;//y1 = x2 - a / b * y2
        return d;
    }
}

//简化版
void exgcd(int a, int b, int &x, int &y){
    if(!b){
        x = 1, y = 0;
        return a;
    }else{
	    int d = exgcd(b, a % b, y, x);
	    y -= a / b * x;
	    return d;
    }    
}
```
- 扩展欧几里得求解线性同余方程
  - 线性同余方程： $a x \equiv b (\mod m)$ 其中a，x，b，m均为整数，x为未知数，方程等价于 $a x = k m + b$ ，也等价于 $a x + m k = b$ 其中x,k均为未知数
  - 方程形如： $a x + b y = c$ 的直线方程，解(x,y)为直线上散列的点
  - 求出a，b的最大公约数 $d = g c d (a, b)$ ，方程化为 $d (x \frac{a}{d} + y \frac{b}{d}) = c$ 易知其中 $x \frac{a}{d} + y \frac{b}{d}$ 为整数，所以要求 $d | c$ ，故 $c = k \cdot d = k \cdot g c d (a, b)$
  - 所以线性同余方程 $a x \equiv b (\mod m)$ 有解的充要条件为b为 $g c d (a, m)$ 的倍数
  - 当 $b \neq k^{'} \cdot g c d (a, m)$ 时( $k^{'}$ 为整数)，方程无解
  - 当 $b = k^{'} \cdot g c d (a, m)$ 时，先用扩展欧几里得求出方程 $a x + m k = g c d (a, m)$ 的特解 $(x, k)$ ，可知 $a x + m k = b$ 方程的解为 $\frac{b}{g c d (a, m)} \cdot (x, k)$ ，所以原式的解为 $\frac{b}{g c d (a, m)} \cdot x$
  - 代码：
```
const int N = 1e5 + 10;
typedef long long LL;
int n; 
int a, b, m;
int x, y;
//扩展欧几里得算法
int exgcd(int a, int b , int &x, int &y){
    if(!b){
        x = 1, y = 0;
        return a;
    }else{
        int t = exgcd(b, a % b, y, x);
        y -= a / b * x;
        return t;
    }
}

int main(){
    cin >> n;
    while(n -- ){
        cin >> a >> b >> m;
        int t = exgcd(a, m, x, y);
        //b是gcd(a,m)的倍数才有解
        if(b % t != 0) cout << "impossible" << endl;
        else cout << (LL)x * (b / t) % m << endl;//特解乘上倍数
    }
    return 0;
}
```
中国剩余定理
- 以后补充