啊啊啊快吐了。。。。。。。。。。

筛质数

埃筛

对于每一个质数，标记它的所有倍数(除了它本身)为合数。
时间复杂度：\(\mathcal {O}(nlog(log(n)))\)。
拓展1：\(1\sim n\) 中质数约有 \(n/ln(n)\) 个。
拓展2：\(1\sim n\) 中质因数约有 \(nlog(log(n))\) 个。（由埃筛复杂度可知）

题目

Prime Distance
很经典，线筛出 \(1\sim \sqrt n\) 区间内的质数，再在区间内埃筛。

线性筛/欧拉筛

埃氏筛的缺点：每个合数会被它的所有质因数标记一次。
欧式筛做到了每个合数只被它的最小质因数标记一次。
设X的最小质因数为 \(P\)，枚举所有小于等于 \(P\) 的质数 \(pi\) ，显然 \(Xpi\) 的最小质因数是 \(pi\)，这样就保证了每个合数只被它的最小质因数标记一次。
同时，如果 \(P\) 是合数 \(X\) 的最小质因数，那么 \(X/P\) 的最小质因数一定大于等于 \(P\)，这就保证了每个合数都会被标记到。
时间复杂度：\(\mathcal {O(n)}\)。

线性筛求 \(1\sim n\) 的逆元

link

例题

瞬间移动

az，先打出 \(1\sim n\) 的逆元表。易推出（实在推不出打表找规律）\(dp[i][j]=dp[i-1][j]+dp[i][j-1]\)。看着很熟悉，最后发现就是斜着的杨辉三角。计算行、列算即可。

另，\(dp[i][j]=dp[i-1][j]+dp[i][j-1]\) 的组合意义也很显然：一共要走 \(i-1+j-1\) 步，在其中选 \(i-1\) 步向下走。

积性函数

常见积性函数

\(φ(n)\)：欧拉函数，\(1\sim n\) 中和 \(n\) 互质的数的个数。
\(μ(n)\)：莫比乌斯函数，如果 \(n\) 的因式分解中有质因数的幂次大于 \(1\) 那么 \(μ(n)=0\)，否则设 \(n\) 有 \(k\) 个质因数，\(μ(n)\)= \((-1)^k\)。
\(d(n)\)：因数函数，n的正因数个数。
\(σ(n)\)：因数和函数，n的所有正因数之和。

\(ϵ(n)\)：单位函数，\(ϵ(1)=1\)，其他情况下 \(ϵ(n)=0\)。完全积性函数。
\(idk(n)\)：幂函数，\(idk(n)=nk\)，其中 \(id1(n)\) 常常写为 \(id(n)\)。完全积性函数。

欧拉函数

给出公式 \(φ(n)=n\prod_{i=1}^{k}(1-\frac {1}{p_i})\)。

观察右边那个累乘，如果将它展开的话，恰好对应一个容斥的过程：\(n\) 个数，减去其中包含 \(n\) 的 \(1\) 个质因数的数，再把同时包含 \(n\) 的 \(2\) 个质因数的数加回来...

积性显然。

特殊的，\(φ(1)=1\)。对于质 数 \(p\) 有 \(φ(p)=p-1\)。对于质数 \(p\) 的 \(x\) 次幂有 \(φ(px)=(p-1)*px-1\)。

因式分解

单个数复杂度：\(\mathcal {O}(\sqrt n)\)。

对于 \(1 \sim n\)，在线性筛的时候处理即可，时间复杂度：\(\mathcal {O}(nlog(log(n))\)。

好简略，还是放个代码吧，实现也挺妙的。

Mobius 函数

计算见定义，积性显然。

特殊的，对于质数 \(p\) 有 \(μ(p)=-1\)。对于质数 \(p\) 的 \(x(x>1)\) 次幂有 \(μ(p^x)=0\)。

因数个数函数

\(d(n)=\prod_{i=1}^k(1+x_i)\)，\(x_i\) 为质数 \(p_i\) 的指数。

由唯一分解定理可以得到上式。积性显然。

特殊的，\(d(1)=1\)。对于质数 \(p\) 有 \(d(p)=2\)。对于质数 \(p\) 的 \(x\) 次幂有 \(d(p^x)=x+1\)。

因数和函数

唯一分解定理可证积性。

\(σ(1)=1\)。对于质数 \(p\) 有 \(σ(p)=p+1\)。对于质数 \(p\) 的 \(x\) 次幂有 \(σ(p^x)=1+p+p^2+……+p^x =σ(p^{x-1})*p+1=(p^{x+1}-1)/(p-1)\)。

线性筛求积性函数

其实有两个通用板子。

1.记录最小因数、最小因数的幂，必要时还可以记录最小因数的个数。在枚举到 \(i\) 时算 \(i\) 的函数。

相当于用空间换时间。（（（

void Prime() {
	for(int i = 2; i <= 500000; i ++) {
		if(!vis[i]) prime[++ tot] = i, minp[i] = minpx[i] = i;
		if(minpx[i] == i) ans[i] = Calc(minp[i], minpx[i]);
		else ans[i] = ans[minpx[i]] * ans[i / minpx[i]];
		for(int j = 1; j <= tot && i * prime[j] <= 500000 && prime[j] <= minp[i]; j ++) {
			vis[i * prime[j]] = 1; minp[i * prime[j]] = prime[j];
			if(prime[j] < minp[i]) minpx[i * prime[j]] = prime[j];
			else minpx[i * prime[j]] = minpx[i] * prime[j];
		}
	}
}

2.不用存这么多，在枚举到 \(i*prime[j]\) 时，暴力除 \(prime[j]\)，直到它没有这个因数，时间复杂度趋近于 \(\mathcal {O}(n)\)，一般常数小于 \(2\)。

代码就懒得放了。

但是，对于一些 \(p^k\) 可以拆成 \(p^{k-1}\) 和 \(p\) 计算的函数（比如欧拉函数），可以用一种更方便的写法，一般人都是用这种写欧拉函数。

代码也懒得放了。。。

求 \(1\sim N\) 中与 \(M\) 互质的数的个数

Way 1. 可以筛出 \(M\) 中所有因数，跑 \(1\sim n\)，\(\mathcal {O}(nlog(n))\)。（这里的 \(log\) 是质因数种类，远比真正的 \(log\) 小）（此方法可以求出具体的那些数与 \(M\) 互质）

Way 2. 还可以利用积性，令 \(gcd_m(n)\) 为 \(n\) 和 \(m\) 的最大公因数，发现这是个积性函数，那么把 \(m\) 的质因数预处理出来，用通用板子直接算即可。更简单地，令 \(f_m(n)\) 表示 \(n\) 是否与 \(m\) 互质，这是完全积性的，质数的时候判断其是否为 \(m\) 因数即可，时间复杂度 \(\mathcal {O(n)}\)。（此方法可以求出具体的那些数与 \(M\) 互质）

Way 3. 容斥。先求出 \(M\) 的质因数，跑 dfs，用到了奇数个就减，偶数个就加，时间复杂度：\(\mathcal {O}(\sqrt M)\)。

求 \(1\sim N\) 中与 \(1\sim M\) 互质的数的个数

考虑对于每个数进行上述的容斥，时间复杂度乍一看是：\(\mathcal {O}(m\sqrt m)\)。其实，对于每个数 \(x\)，只有其倍数容斥时用到了它，复杂度可看作 \(\mathcal {O}(\mathrm {n{ln}\ m})\)。这个 \(\mathrm {ln}\) 跑不满，\(m=10^5\) 时大概为 \(7\)。

for(int i = 1; i <= n; i ++) dp[i] = n;
for(int i = 1; i <= n; i ++) { // f[i] 容斥系数，线性筛预处理 
	if(f[i] > 1) continue;
	for(int j = i; j += n; j ++) dp[j] += (f[i] ? -1 : -1) * n / j;
}

例题

link

题意：
给定 \(M\) 和 \(K\)，求所有和 \(M\) 互质的正整数中第 \(K\) 小的。
数据范围：\(1<=M<=1e6，1<=K<=1e8\)。

二分+容斥可做到 \(log_2(maxval) \times\sqrt M\)。

因为 \(\gcd(a,b)=\gcd(a+b,b)\)，所以其实只需要算小于等于 \(M\) 的。用上述方法即可（求 \(1\sim N\) 中与 \(M\) 互质的数的个数）。

欧拉定理

啊啊啊啊啊啊啊啊啊。。。。

欧拉定理：
对于互质的两个正整数 \(a\) 和 \(m\)，有 \(a^{φ(m)} ≡ 1 (\mathrm {mod\ m})\)

证明：
设 \(x1,x2,...xφ(m)\) 是 \(1\sim m\) 中与 \(m\) 互质的 \(φ(m)\)个数，也称为 \(m\) 的缩系。
因为 \(a\) 也与 \(m\) 互质，所以 \(a*x1,a*x2,...,a*x_{φ(m)}\)也都与 \(m\) 互质，而且他们之间在模 \(m\) 意义下互不相等。所以 \(a*x1,a*x2,...,a*x_{φ(m)}\) 也是 \(m\) 的缩系。
所以 \(∏x_i ≡ ∏(a*x_i) ≡ a^{φ(m)}*∏x_i (\mathrm {mod\ m})\)，所以 \(a^{φ(m)} ≡ 1 (\mathrm {mod\ m})\)。

拓展：如果 \(a\) 和 \(m\) 互质，那么 $ a^n ≡ a^{n%φ(m)} (\mathrm {mod\ m})$。不互质的时候要用扩展欧拉定理。

欧拉定理求逆元

当 \(m\) 为质数，\(φ(m)=m-1\)，且任意 \(1\sim m-1\) 的正整数都与 \(m\) 互质，这种特殊情况就是费马小定理。此时 \(a^{m-1} ≡ 1 (\mathrm {mod\ m})\)，则 \(a^{m-2} ≡ a^{-1} (\mathrm {mod\ m})\)。

阶

对于互质的两个正整数 \(a\) 和 \(m\)，使得 \(a^n ≡ 1 (\mathrm {mod\ m})\) 成立的最小正整数 \(n\) 称为模 \(m\) 意义下 \(a\) 的阶，记作 \(ord_m(a)\)。\(ord_m(a)\) 一定是 \(φ(m)\) 的因数。
如果模 \(m\) 意义下 \(a\) 的阶是 \(n\)，那么在模 \(m\) 意义下 \(a^0,a^1,...,a^{n-1}\) 互不相同。证明很显然：如果存在 \(0≤i<j≤n-1\) 满足 \(a^i ≡ a^j (\mathrm{mod\ m})\)，那么 $a^{j-i} ≡ 1 (\mathrm {mod\ m}) $且 \(j-i<n\)，这与 \(n\) 是 \(a\) 模 \(m\) 意义下的阶相冲突。

原根

对于互质的两个正整数 \(a\) 和 \(m\)，如果 \(ord_m(a)=φ(m)\)，我们称 \(a\) 是 \(m\) 的一个原根，此时$a^0,a1,...,a^{φ(m)-1} $互不相同。
如果 \(a\) 是 \(m\) 的一个原根，当且仅当 \(GCD(b,φ(m))=1\)，\(a^b\)也是 \(m\) 的一个原根。证明如下：\((a^b)^{ord(a^b)} ≡ 1 (\mathrm {mod\ m})\) 所以 \(ord(a^b)=φ(m)/GCD(φ(m),b)\)。当且仅当 \(b\) 和 \(φ(m)\) 互质时\(ord(ab)=φ(m)\)，此时 \(a^b\) 是 \(m\) 的原根。

原根存在定理

当且仅当 \(m=1、2、p^a或2p^a\) 时，\(m\) 有原根。（证明需要用到群论）

原根个数

如果 \(m\) 存在原根，那么原根的个数为 \(φ(φ(m))\),证明如下：设 \(q\) 为 \(m\) 的一个原根，当且仅当\(GCD(b,φ(m))=1\)，\(q^b\) 也是 \(m\) 的原根。这样的 \(b\) 有 \(φ(φ(m))\) 个。

注意 \(q\) 只是任意一个。

威尔逊定理

当且仅当 \(p\) 是素数时，\((p-1)! ≡ p-1 (\mathrm {mod\ p})\)。

证明(1)：
如果p不是素数，那么我们分以下三种情况来证明(p-1)! ≠ p-1 (mod p)。
p=4时，(p-1)! ≡ 3! ≡ 2 (mod p)。
p>4且是完全平方数时，p = aa且a>2，因为a2a ≡ 0 (mod p)，且2a≤p-1，所以(p-1)! ≡ 0(mod p)。
p>4且不是完全平方数时，p可表示为两个不相等整数的积a*b，其中1<a且1<b，因为a≤p-1且b≤p-1，所以(p-1)! ≡ 0 (mod p)。
证明(2)：
当p是素数时，在模p意义下1~p-1中满足a2 ≡ 1 (mod p)的仅有1和p-1，对于其他数字中不相等的两个数字a和b，a-1 ≠ b-1 (mod p)，所以其他数字可以两两配成乘积为1的数对，所以(p-1)! ≡ p-1 (mod p)。

（懒得改latex了）

例题：Fansblog

快速求出 \(Q\) 的阶乘是很难的。但 \(Q\) 离 \(P\) 很近，不妨用威尔逊定理，算出 \((P-1)!\)，再倒着算。