欧拉函数的power

在算数基本定理中有 $ N = p_{1}^{a1} p_{2}^{a2} p_{3}^{a3} ..... p_{k}^{ak} $
wuw在y总的课中是用了容斥原理进行推导

得到了
$ \phi(x) = N * (1 - \frac{1}{p1}) * (1 - \frac{1}{p2}) * .... * ( 1 - \frac{1}{pk}) $
所以就可以得到依靠该公式得出的欧拉公式的算法

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
int n;
//f(x) = x(1 - 1/p1)(1-1/p2)...(1-1/pk);
int main()
{
    cin >> n;
    while (n -- ){
        vector<int> res;
        int x;
        cin >> x;int c = x;
        for(int i = 2; i <= x / i; i ++)
        {
            if(x%i == 0){
                while(x % i == 0)
                {
                    x /= i;
                }
                res.push_back(i);
            }
        }
        if(x > 1)
            res.push_back(x);
        
        for(auto t: res)
        {
         //   cout << t << ' ';
            c = c - c / t;
        }
        cout << c << endl;
    }
    return 0;
}

but 这样做因为存在着分解质因数的时间复杂度为 \(O(\sqrt{a})\)
加上要进行n次所以最后的时间复杂度是 \(O(\sqrt{a}* n)\)
所以可以引进之前学习的线性筛（欧拉筛）
设数组phi[N]表示 \(\phi(x)\)
因为 数组pri是记录质数的存在 1~pri[i]与pri[i]互质的数的个数一定是 pri[i] - 1所以phi[pri[i] = pri[i] - 1
所以在质数筛过程中进行的 st[pri[j] * i]操作时就可以有两种情况
当 i % pri[j] == 0时
这个时候 pri[j] 和 i 的 因子是相同的所以$ \phi(i) $ 和 \(\phi(pri[j] * i)\) 仅仅是后者多乘了一个 pri[j] 就有phi[i * pri[j]] = pri[j] * phi[i];
另一种情况时
此时因子不同 要在乘一个(1 - \(\frac{1}{pri[j]}\)) 和 pri[j]所以就有 phi[i * pri[j]] = phi[i] * (pri[j] - 1);

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e6 + 10;
bool st[N];
int pri[N],cnt;
int phi[N];
int main()
{
    int n;
    cin >> n;
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i])
        {
            pri[cnt ++] = i;
            phi[i] = i - 1;
        }
        for(int j = 0; pri[j] <= n / i; j ++)
        {
            st[pri[j] * i] =true;
            if(i % pri[j] == 0)
            {
                phi[i * pri[j]] = pri[j] * phi[i];
                break;
            }
            phi[i * pri[j]] = phi[i] * (pri[j] - 1);
        }
    }
    phi[1] = 1;
    long long sum = 0;
    for(int i = 1; i <= n; i ++)
        sum += phi[i];//cout << phi[i] << ' ';
    cout << sum;
    return 0;
}

可以做到时间复杂度为 $ O(n) $