模板索引：数学相关

基本数论

基本概念

1. 整除：对两个正整数 \(a, b \ (b \le a)\)，如果存在一个整数 \(k\)，使得 \(a = bk\)，则称 \(b\) 整除 \(a\)，记作 \(b | a\)。
2. 算术基本定理：对任何一个大于 \(1\) 的整数 \(x\)，\(x\) 均能表示成若干个 \(x\) 的质因子的乘积。且这个表示法是唯一的。
3. 因数：对一个正整数 \(x\)，所有能整除 \(x\) 的正整数均为 \(x\) 的因
   数。
4. 质数：因数只有 \(1\) 和自身的正整数叫质数；\(1\) 不是质数。
5. 互质的定义：\(gcd(a, b) = 1\) .
6. 因数分解：\(O(\sqrt{x})\) 对任意正整数 x 分解因子。
7. 质因子分解：\(O(\sqrt{x})\) 对任意正整数 x 分解质因子。
8. 欧几里得算法：\(gcd(a, b) = gcd(b, a \mod b)\)

线性筛

点击查看代码

void prime(){for(int i = 2; i <= n; i++){if(!vis[i]) p[++cnt] = i;for(int j = 1; j <= cnt && 1ll * i * p[j] <= n; j++){vis[i * p[j]] = 1;if(i % p[j] == 0) break;}}
}

此外，如果预处理每次记下 \(n\) 的最小质因子，那么可以 \(O(log n)\) 完成一次质因子分解。

二元一次不定方程

方程 \(ax + by = c\) 有解当且仅当 \(gcd(a, b) | c\).

点击查看代码

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

欧拉函数

• 定义欧拉函数 \(φ(n)\) 表示小于 \(n\) 的数中与 \(n\) 互质的数的个数。（定义为小于等于不会影响，因为gcd(n, n） = n; 显然不影响计数。
• 特别的，\(φ(1) = 1\)

欧拉函数的性质

• 积性：如果 \(\gcd(a,b)=1\)，则 \(\varphi(a\times b)=\varphi(a)\times \varphi(b)\)。
• 欧拉反演：\(\sum_{d\mid n}\varphi(d)=n\)。
• 性质三：对任意质数 \(p\)，\(\varphi(p^k)=p^k-p^{k-1}\)。（证明：显然只有 \(p,2p,3p,\ldots,p^{k-1}p\) 与 \(p^k\) 不互质，共 \(p^{k-1}\) 个。）

计算欧拉函数

• 单个欧拉函数：设 \(n\) 的唯一分解式是 \(n=p_1^{k_1}p_2^{k_2}\cdots p_s^{k_s}\)。根据积性，\(\varphi(n)=\prod_{i=1}^{s}\varphi!\left(p_i^{k_i}\right)\)。后者根据性质三可计算。

• 线性筛欧拉函数：在线性筛的同时可以筛出欧拉函数，设 \(p\) 是 \(i\) 的最小质因子，分三种情况讨论：

  1. \(i\) 为质数：\(\varphi(i)=i-1\)
  2. \(p\) 是 \(\dfrac{i}{p}\) 的质因子：\(\varphi(i)=\varphi\left(\dfrac{i}{p}\right)\times p\)
  3. \(p\) 和 \(\dfrac{i}{p}\) 互质：\(\varphi(i)=\varphi\left(\dfrac{i}{p}\right)\varphi(p)\)