数学笔记:数论
欧拉函数(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(完全积性)
更多内容可以参见积性函数 – 维基百科,自由的百科全书