$\Huge\color{orchid}{点击此处获取更多干货}$

欧拉筛&欧拉函数

忘了欧拉筛的话，可以点这里回顾
上次提到的欧拉函数$\phi(x)$，它可以衍生出以下几个推论：
1. $\phi(1)=1$，当$x$是质数时$\phi(x)=x-1$
2. 当$i\%p=0$时，$\phi(i*p)=\phi(i)*p$
3. 当$i\%p \ne 0$时，$\phi(i*p)=\phi(i)*(p-1)$

重点解释一下2和3：(以下不带下标的$p$都表示质数)
当$i\%p=0$时，令$x=i*p$，则$p$是$i$的一个约数，它必然也是$i$的质因数，从不大于$x$的整数中选出一个数，使其不能被$x$的质因数整除的概率仍然还是$\prod (1-1/p_i)$，其中$p_i$是$i$的质因数。用它乘上$x$就可得$\phi(x)=\phi(i)*p$

当$i\%p\ne 0$时，$x$使用相同定义，则$p$成为了$x$的新质因数，它不再是$i$的质因数，从不大于$x$的整数中取出一个数，使其不能被$x$的质因数整除的概率除了上面提到的$\prod (1-1/p_i)$，还得再乘上$(1-1/p)$，这个时候再用$x$去乘，分母上的$p$就会将$x$约成$i$，多出一项$(p-1)$，然后$i$和剩下的部分组成欧拉函数$\phi(i)$，得$\phi(x)=\phi(i)*(p-1)$

之所以会提到这两个性质，是因为欧拉筛中，存在$i\%primes[j]$这样的判断。加上欧拉筛之后，不大于某个值$N$的所有欧拉函数值都可以在筛的过程中，利用上面的三条推论求出。如果将所有求出的欧拉函数保存起来，甚至还可以取得欧拉函数的前缀和

C++ 代码

/**
 * @class 
 * @brief 欧拉函数前缀和求解
 * class也可以用于制作仿函数，信息隐藏能力更好
 */
class EulerFunction {
public:
    /**
     * @brief 求解1~n的欧拉函数前缀和
     * @param n 上限
     * @return 该段前缀和
     * 把各表的构造放在了()重载函数中，因此该仿函数只能一次性使用
     */
    size_t operator()(int n) {
        isComposite = new int[n + 1]();
        primes = new int[n];
        phi = new size_t[n + 1]();
        phi[1] = 1;                             //记录所有欧拉函数值，phi(1)=1
        for (int i = 2; i <= n; i++) {
            if (!isComposite[i]) {              //遇上了质数i，将其函数值赋为i-1
                primes[size++] = i;
                phi[i] = i - 1;
            }
            for (int j = 0; j < size; j++) {
                if (i * primes[j] > n) {
                    break;
                }
                isComposite[i * primes[j]] = 1;
                if (i % primes[j] == 0) {       //之后在欧拉筛的基础上，对应求出两种不同情况的欧拉函数
                    phi[i * primes[j]] = phi[i] * primes[j];
                    break;
                }
                else {
                    phi[i * primes[j]] = phi[i] * (primes[j] - 1);
                }
            }
        }
        size_t sum = 0;
        for (int i = 1; i <= n; i++) {          //最后把它们累加起来
            sum += phi[i];
        }
        return sum;
    }

    ~EulerFunction() {
        delete[] isComposite, primes, phi;
    }
private:
    int* isComposite = nullptr, * primes = nullptr;
    size_t* phi = nullptr;
    size_t size = 0;
};