网站建设 部署与发布题库,微信头像做国旗网站,韶关建设网站,开发游戏的职业叫什么文章目录 欧拉函数定义性质计算公式求某个数欧拉函数值线性筛求区域内欧拉函数 欧拉函数
定义
在[1,n]的范围内所有与n互质的数字的个数。
我们用 φ ( n ) \varphi(n) φ(n)来表示数字n的欧拉函数的值#xff0c;例如#xff1a; φ ( 4 ) 2 \varphi(4)2 φ(4)2#xf… 文章目录 欧拉函数定义性质计算公式求某个数欧拉函数值线性筛求区域内欧拉函数 欧拉函数
定义
在[1,n]的范围内所有与n互质的数字的个数。
我们用 φ ( n ) \varphi(n) φ(n)来表示数字n的欧拉函数的值例如 φ ( 4 ) 2 \varphi(4)2 φ(4)2与在[1,4]中与4互质的数字是1 3有两个因此 φ ( 4 ) 2 \varphi(4)2 φ(4)2
性质
如果n是一个质数 φ ( n ) n − 1 \varphi(n)n-1 φ(n)n−1如果n是一个质数则存在 n k n^k nk则 φ ( n k ) ( n − 1 ) ⋅ n k − 1 \varphi(n^k)(n-1) \cdot n^{k-1} φ(nk)(n−1)⋅nk−1积性函数如果 g c d ( m , n ) 1 gcd(m,n)1 gcd(m,n)1则 φ ( m n ) φ ( m ) ⋅ φ ( n ) \varphi(mn)\varphi(m)\cdot \varphi(n) φ(mn)φ(m)⋅φ(n)
计算公式
根据整数唯一分解定理 n ∏ i 1 s p i a i n\prod_{i1}^{s}p_i^{a_i} n∏i1spiai即任何一个正整数都可以分解为若干个质数的 a i a_i ai次幂的连乘积其中 s s s为质因子的个数。
因此 φ ( n ) ∏ i 1 s φ ( p i a i ) ∏ i 1 s ( p i − 1 ) ⋅ p i a i − 1 ∏ i 1 s ( 1 − 1 p i ) ⋅ p i a i n ⋅ ∏ i 1 s p i − 1 p i \varphi(n)\prod_{i1}^{s} \varphi(p_i^{a_i}) \prod_{i1}^{s}(p_i -1)\cdot p_i ^{a_{i} -1} \prod_{i1}^{s}(1- \frac{1}{p_i}) \cdot p_i^{a_i}n\cdot \prod_{i1}^{s}\frac{p_i -1}{p_i} φ(n)∏i1sφ(piai)∏i1s(pi−1)⋅piai−1∏i1s(1−pi1)⋅piain⋅∏i1spipi−1
因此我们可以得到欧拉函数的计算公式 φ ( n ) n ⋅ p 1 − 1 p 1 ⋅ p 2 − 1 p 2 ⋯ p s − 1 p s \varphi(n) n \cdot \frac{p_1-1} {p1} \cdot \frac{p_2-1}{p2} \cdots\frac{p_s-1}{p_s} φ(n)n⋅p1p1−1⋅p2p2−1⋯psps−1
通俗来讲 n n n的欧拉函数值就是 n n n对每个质因数分解所得到的质因数进行操作后的连乘积 然后再乘一个 n n n。
因此欧拉函数的值与n和他的质因子有关与项数无关。 求某个数欧拉函数值
根据我们刚才得到的欧拉函数的计算公式可以得到某个值的欧拉函数的值我们可以使用试除法来计算
typedef long long ll;
//1. 试除法求欧拉函数某一个确切的值的欧拉函数
ll fun1(int n){ll phin;for (int i2;1ll*i*in;i){ //防止溢出if (n%i0){ //如果是一个质因子phiphi/i*(i-1); //计算欧拉函数值while (n%i0){ //分解质因子n/i;}}}if (n1){phiphi/n*(n-1); //最后还剩其自身}return phi;
}线性筛求区域内欧拉函数
如果 n n n 是质数则 φ ( n ) n − 1 \varphi(n)n-1 φ(n)n−1 在线性筛中一个合数一定是被他的最小质因子筛掉的。假设这个最小质因数是 p j p_j pj因此一定存在一个 m p j ⋅ i mp_j \cdot i mpj⋅i 此时会出现两种情况
如果 i i i 能够被 p j p_j pj 整除则 i i i 一定包含了 p j p_j pj 的所有质因子因此我们可以得到 φ ( m ) m ⋅ ∏ k 1 s p k a k p j ⋅ i ⋅ ∏ k 1 s p k a k p j ⋅ φ ( i ) \varphi(m)m \cdot \prod_{k1}^{s}p_k^{a_k} p_j \cdot i \cdot \prod_{k1}^{s}p_k^{a_k} p_j \cdot \varphi(i) φ(m)m⋅∏k1spkakpj⋅i⋅∏k1spkakpj⋅φ(i)如果 i i i 不能被 p j p_j pj 整除则 i i i 与 p j p_j pj 一定是互为质数的因此有以下式子 φ ( m ) φ ( p j ) ⋅ φ ( i ) φ ( i ) ⋅ ( p j − 1 ) \varphi(m)\varphi(p_j) \cdot \varphi(i) \varphi(i) \cdot (p_j-1) φ(m)φ(pj)⋅φ(i)φ(i)⋅(pj−1)
并且通过这种线性筛我们可以得到 [ 1 , n ] [1,n] [1,n]范围内的所有的数字的欧拉函数。
最后代码如下
//2. 筛法求欧拉函数任意范围内的数值
const int N1e810;
int primes[N]; //存储质数
bool vis[N];
int phi[N]; //存储每个数字的欧拉哈数
std::vectorint vec;
void fun2(int n){int cnt0;for (int i2;in;i){if (!vis[i]){primes[cnt]i;//质数i的欧拉函数就是i-1phi[i]i-1;}for (int j1;1ll*i*primes[j]n;j){int mi*primes[j];vis[m]true;if (i%primes[j]0){phi[m]phi[i]*primes[j];break; //整除中断}else{phi[m]phi[i]*(primes[j]-1);}}}
}
