Codeforces Round #670 (Div. 2) 题解
[CF1406A] Subset Mex 提交地 …
标签： 素数筛
![[NOI2010]能量采集 题解](https://ksmeow.moe/wp-content/uploads/2018/05/180516a.jpg "180516a")
数学笔记：数论
欧拉函数（Eular’s Totient Function）
定义
在数论中，对正整数n，欧拉函数\varphi(n)是小于或等于n的正整数中与n互质的数的数目。
规定：\varphi(1) = 1
费马小定理（Fermat’s Little Theorem）
若a是一个整数，p是一个质数，则
a^{p-1} \equiv 1 \ (mod \ p)
欧拉定理（Eular’s Theorem (Number Theory)）
若n，a为正整数，且gcd(n, a) = 1，则
a^{\varphi(n)} \equiv 1 \ (mod \ n)
欧拉函数值的求解
直接公式求解
欧拉函数的值计算有以下公式
\varphi(x) = x (1 - \frac{1}{p_1}) (1 - \frac{1}{p_2}) \cdots (1 - \frac{1}{p_k})
其中p_i代表x的质因数。
因此我们可以枚举x的质因数，并计算\varphi(x)的值。
这个算法单次计算的复杂度是O(\sqrt{n})。
线性筛法求解
本方法适用于求1至n的函数值计算。
首先，我们知道欧拉函数是一个积性函数，即\varphi(nm) = \varphi(n) \varphi(m)。
对于素数，它的函数值就是它本身减1。对于非素数，我们想到了线性筛法的避免重复计算条件：prime[j]是i的一个因数。此时，我们已经知道了\varphi(prime[j])和\varphi(i)，那么可以算出\varphi(i \cdot prime[j]) = \varphi(i) \varphi(prime[j])。
这个算法的复杂度是O(n)。
代码实现如下：
inline void phi_solve(int n) {
phi[1] = 1;
for(int i = 2; i <= n; i++) {
if(!vis[i]) {
prime[tot++] = i;
phi[i] = i - 1;
}
for(int j = 0; j < tot; j++) {
vis[i * prime[j]] = true;
if(i % prime[j] == 0) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
} else {
phi[i * prime[j]] = phi[i] * phi[prime[j]];
}
}
}
}
阶（Order）
定义
若a，p为正整数，且gcd(a, p) = 1，称满足a^r \equiv 1 \ (mod \ p)的最小正整数r为a模p的阶，记作Ord_p(a)。
常用性质
- 若a，p为正整数，且gcd(a, p) = 1，r为a模p的阶，若有正整数m满足a^m \equiv 1 \ (mod \ p)，则r|m。
- 若a，p为正整数，且gcd(a, p) = 1，r为a模p的阶，则r|\varphi(m)。
- 若a，p为正整数，且gcd(a, p) = 1，a^i \equiv a^j \ (mod \ p)当且仅当i \equiv j \ (mod \ Ord_p(a))。
求解阶
没什么好办法，从小到大枚举r并判断是否是阶。
原根（Primitive Root）
定义
若a，p为正整数，且gcd(a, p) = 1，称满足Ord_p(a) = \varphi(p)的a叫做模p的一个原根。
注意：不是任何p都存在原根。每个素数都存在原根。
常用性质
- 当a为m的原根时，a^0, a^1, a^2, \cdots, a^{m-1}构成了m的一个简化剩余类。
- 模m有原根的充要条件是m=2, 4, p^n, 2p^n，其中p为奇素数，n为任意正整数。
求解原根
我们知道了上述阶的性质2，要判断某数是不是模m的原根，可以验证是否存在m-1的一个约数a满足g^a \equiv 1 \ (mod \ m)，如果有的话那么g的阶就不是m-1，则g不是模m的原根。
一般来说原根不会很大，从2开始枚举并按照上述方法判断就可以得到。
代码如下
inline int solve_g(int m) {
// 预处理出因数
int fact[105], tot = 0, x = m - 1;
for(int i = 2; i * i <= x; i++) {
if(x % i == 0) {
fact[tot++] = (m - 1) / i;
while(x % i == 0) x /= i;
}
}
if(x > 1) fact[tot++] = (m - 1) / x;
// 枚举原根
bool success;
for(int i = 2;; i++) {
success = true;
for(int j = 0; j < tot; j++) {
if(fpow(i, fact[j], m) == 1) {
success = false;
break;
}
}
if(success) return i;
}
}
注：代码中fpow()函数是快速幂取模。
应用：乘法换加法（取模意义下）
我们知道，任何一个小于正整数m的正整数都可以表示为原根的某次幂，那么求一个由小于m正整数组成的数列的累乘值可以转化为原根的指数求和，这样可以不用计算高精度，且由周期性还可以缩小指数的范围。
例题：[SDOI2015]序列统计
题目描述
小C有一个集合S，里面的元素都是小于M的非负整数。他用程序编写了一个数列生成器，可以生成一个长度为N的数列，数列中的每个数都属于集合S。小C用这个生成器生成了许多这样的数列。但是小C有一个问题需要你的帮助：给定整数x，求所有可以生成出的，且满足数列中所有数的乘积mod M的值等于x的不同的数列的有多少个。小C认为，两个数列{Ai}和{Bi}不同，当且仅当至少存在一个整数i，满足Ai≠Bi。另外，小C认为这个问题的答案可能很大，因此他只需要你帮助他求出答案mod 1004535809的值就可以了。
输入输出格式
输入格式：
一行，四个整数，N、M、x、|S|，其中|S|为集合S中元素个数。第二行，|S|个整数，表示集合S中的所有元素。
输出格式：
一行，一个整数，表示你求出的种类数mod 1004535809的值。
输入输出样例
输入样例#1：
4 3 1 2 1 2
输出样例#1：
8
说明
【样例说明】
可以生成的满足要求的不同的数列有(1,1,1,1)、(1,1,2,2)、(1,2,1,2)、(1,2,2,1)、(2,1,1,2)、(2,1,2,1)、(2,2,1,1)、(2,2,2,2)。
【数据规模和约定】
对于10%的数据，1<=N<=1000；
对于30%的数据，3<=M<=100；
对于60%的数据，3<=M<=800；
对于全部的数据，1<=N<=109，3<=M<=8000，M为质数，1<=x<=M-1，输入数据保证集合S中元素不重复
解释
对于本题我们需要求出数列中所有元素的乘积，我们可以应用乘法转加法得到数列乘积的原根指数，再将x处理成原根的某次幂，根据阶的性质3即可判定是否同余。
本题的完整题解参见[SDOI2015]序列统计 题解 | KSkun’s Blog。
威尔逊定理（Wilson’s theorem）
当且仅当p为素数时，有 (p-1)! \equiv -1 \pmod{p} 。
积性函数（Multiplicative function）
定义
积性函数是指一个定义域为正整数n的数论函数f(n)，有如下性质：
\begin{aligned} & f(1) = 1 \\ & f(ab) = f(a)f(b) & (a, b) = 1 \end{aligned}
如果上述性质中，不要求a、b互质，即不只a、b互质的情况下都有f(ab) = f(a)f(b)，则f(n)为完全积性函数。
常见的积性函数
- \varphi(n)：欧拉函数
- \mu(n)：莫比乌斯函数
- \mathrm{gcd}(a, k)：最大公因数（当k为定值时）
- 1(n)：常函数，定义为1(n)=1（完全积性）
更多内容可以参见积性函数 – 维基百科，自由的百科全书
