当前位置：首页 > article >正文

筛法求欧拉函数

article 2024/9/21 10:35:08

如果只给定一个数 n ，那么这个方法可以求区间 1-n 之间任何一个数的欧拉函数

step1：

初始化 phi[1] = 1，代表 1-1 之间与 1 互为质数的数只有 1 个，就是 1

step2：

运用线性筛法。对于一个质数 p 而言，根据互质的概念（如果数 p 与数 i 互质，那么它们只有1一个公约数），在 1-p 中与 p 互质的数的个数是 p-1 个，就是 1-(p-1) 这个区间内的所有数

线性筛法：http://t.csdnimg.cn/BLddK

step3：

当 i % primes[j] == 0 时，说明 primes[j] 是 i 的最小质因数（因为 primes[j] 中记录的质数符合从小到大的规律），那么 primes[j]*i 这个数的质因数种类和i的质因数种类相同，那么：

$\phi(primes[j]*i) = (primes[j]*i)(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})$

$\phi(i) = i(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})$

这两个公式和质因数的质数完全无关，说明两个公式中的 $(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})$ 应该是完全相同的。

所以 $\phi(primes[j]*i) = \phi(i)*primes[j]$

step4：

当 i%primes[j] != 0 时，说明 primes[j] 比 i 的最小质因数还要小，说明 primes[j]*i 的质因数相较于i的质因数还要多一个 primes[j] ，所以：

$\phi(primes[j]*i) = (primes[j]*i)(1-\frac{1}{primes[j]})(1-\frac{1}{p_1})...(1-\frac{1}{p_k})$

$\phi(i) = i(1-\frac{1}{p_1})...(1-\frac{1}{p_k})$

同样的，这两个公式中的 $(1-\frac{1}{p_1})...(1-\frac{1}{p_k})$ 应该是一样的，所以：

$\phi(primes[j]*i) = \phi(i)*primes[j]*(1-\frac{1}{primes[j]})$

$= \phi(i)*(primes[j]-1)$

step5：

结束之后，phi 数组中记录的就应该是 1-n 中所有数的欧拉函数值，如 phi[6] 记录的就是 1-6 之间与 6 互质的数的个数

题目如下：

给定一个正整数 n，求 1∼n 中每个数的欧拉函数之和。

输入格式

共一行，包含一个整数 n。

输出格式

共一行，包含一个整数，表示 1∼n 中每个数的欧拉函数之和。

数据范围

1≤n≤106

代码如下：

#include<iostream>
#include<cstring>

using namespace std;

typedef long long ll;

const int N = 1000010;

int primes[N],k;
int phi[N];//如phi[9]，用来记录1-9之间与9互质的数的个数是多少
int n;
bool st[N];

void euler(int n)
{
    phi[1] = 1;//1-1之间，与1互质的数的个数只有1本身
    
    for (int i = 2;i<=n;++i)
    {
        if (st[i] == false)
        {
            primes[k++] = i;
            phi[i] = i-1;//如果一个数i是质数，那么在1-i区间内，和i互质的数的个数是i-1个
                         //互质定义：如果p和i互质，那么这两个数的公约数只有1
        }
        for (int j = 0;primes[j] <= n/i;++j)
        {
            st[primes[j]*i] = true;
            if (i%primes[j] == 0)
            {
                phi[primes[j]*i] = phi[i]*primes[j];//（1）
                break;
            }
            phi[primes[j]*i] = phi[i] * (primes[j]-1);//（1）
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    
    euler(n);
    
    ll res = 0;
    for(int i = 1;i<=n;++i)
    res += phi[i];
    
    cout << res << endl;
    return 0;
}