欧拉函数

欧拉函数：φ(n)即在1~n中与n互质的数的个数φ(1) = 1， φ(2) = 1， φ(3) = 2，φ(4) = 2，φ(5) = 3，φ(6) = 2（即1、5）

对于一个数N肯定等于它的质因子的指数和：N = p1^φ1 + p2^φ2 + ……+pk^φk。

那么求该数的欧拉函数等于：φ(N) = N(1 - 1 / p1)(1 - 1 / p2)(1 - 1 / p3)……(1 - 1 / pk)，比如φ(6) = 6 * 1 / 2 * 2 / 3 = 2。

用容斥原理来证明：1 ~ N中与N互质的数的个数φ(N)

前置知识：N的质因子为p1, p2,……,pk, N = p1^φ1 + p2^φ2 + ……+pk^φk。被1整除的个数为n, 被2整除的个数为 n / 2, 被3整除的个数为 n / 3, ……，那么被前n个数整除的个数加起来：n * (1+1/2+1/3+1/4+...1/n) = n * (ln(n+1) + r), Euler近似地计算了r的值，约为0.5772156649。这个数字就是后来称作的欧拉常数。

1、从N中分别去掉它所有质因子p1、p2、……、pk的所有倍数

φ(N) = N - N / p1 - N / p2 - N / p3 - …… - N / pk; 比如6的质因子2、3, 去除2的倍数个数：6 / 2 = 3(2, 4, 6), 去除3的倍数个数：6 / 3 = 2(3，6）

2、因为上面会多去除一次pi*pj的倍数，如上就多去除了2 * 3的倍数6，所以要加过来。

φ(N) = N - N / p1 - N / p2 - N / p3 - …… - N / pk + N / p1p2 + N / p1p3 + N / p2p3 + ……

3、根据容斥原理，

正中间的区域G又被抵消掉了，变成没有加进来，但是我们要把它去掉（因为p1p2p3质因子的乘积肯定与N不互质）

φ(N) = N - N / p1 - N / p2 - N / p3 - …… - N / pk + N / p1p2 + N / p1p3 + N / p2p3 + ……-N / p1p2p3 - N / p1p2p4-……+ N / p1p2p3p4……

φ(N) = N(1 - 1 / p1)(1 - 1 / p2)(1 - 1 / p3)……(1 - 1 / pk)

比较这两个式子，全部乘1后，可以得到N，-1 / p1乘以所有1后得到也是负数，即 -N/p1；-1/p1*-1/p2 = 所以1 / p1p2的常数项是正的。

简单推论发现上面即是下面的展开项。

*给定n个正整数

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        int res = x;
        for(int i = 2;i <= x / i; i++)
        {
            if(x % i == 0)
            {
                res = res / i * (i - 1);
                while(x % i == 0) x /= i;
            }
        }
        if(x > 1) res = res / x * (x - 1);
        
        cout<<res<<endl;
    }
    
}

注意：本来这里是res = res * (1 - 1 / i) = res * (i - 1) / i;但这样写会出错，可能会导致某个地方无法整数

要写成 res = res / i * (i - 1); res = res / x * (x - 1);

筛法求欧拉函数：

题目描述
给定一个正整数n，求1~n中每个数的欧拉函数之和。
数据范围：1≤n≤10^6

#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long LL;
const int N = 1e6 + 10;
int primes[N], phi[N], cnt;
bool st[N];

LL get_eulers(int n)
{
    phi[1] = 1;
    for(int i = 2;i <= n; i ++)
    {
        if(!st[i])
        {
            primes[cnt++] = i;
            phi[i] = i - 1;
        }
            for(int j = 0;primes[j] <= n / i; j++)
            {
                st[i * primes[j]] = true;
                if(i % primes[j] == 0) 
                {
                    phi[primes[j] * i] = primes[j] * phi[i];
                    break;
                }
                phi[primes[j] * i] = phi[i] * (primes[j] - 1);
            }
    }
    LL res = 0;
    for(int i = 1; i <= n; i++) res += phi[i];
    
    return res;
}

int main()
{
    int n;
    cin>>n;
    
    cout<<get_eulers(n)<<endl;
    
    return 0;
}

1、首先对于指数i的欧拉函数：φ(i) = i - 1(前i - 1个数都与它互质）

2、如果 i % p[j] == 0, 此时i是合数，且p[j]是i的最小质因子，那么φ(i * pj)的质因子与φ(i)的质因子完全相同，(1 - 1 / pj)已经在φ(i)中计算过了，只需要乘以一个pj就行了，那么φ(i) = i * (1 - 1 / p1)(1 - 1 / p2)……（1 - 1 / pk)，φ(i * p[j]) = p[j] * φ(i) ;

3、如果i % p[j] != 0, p[j]是 i * p[j]的最小质因子，pj不包含在 i 的质因子当中。根据之前对线性筛的分析，这时候 i 和 pj肯定都是质数，且pj <= i.

φ(i) = i * (1 - 1 / p1)(1 - 1 / p2)……（1 - 1 / pk)，φ(i * p[j])比φ(i)多了一个质因子p[j], 所以要多乘以一个（1 - 1 / pj)：

φ(i * p[j]) = p[j] * i * (1 - 1 / p1)(1 - 1 / p2)……（1 - 1 / pk)(1 - 1 / pj) = (pj - 1)φ(i)。

所以

i % p[j] == 0 时：phi[primes[j] * i] = primes[j] * phi[i];
i % p[j] != 0 时：phi[primes[j] * i] = (primes[j] - 1) * phi[i];
于是得证。