.欧拉函数.

先介绍欧拉函数：
贴一张

证明：

这里利用容斥原理来进行证明：若要求1~N当中与N互质的个数，则应在1~N当中去除N的质因数的倍数，因为既然是因数，那么一定不与N互质，既然是N的因数，那么一定是N的质因数的倍数。对于上述公式里的质因数pi来说，在1~N上pi倍数的个数即为N/pi
那么1~N中与N互质的个数即为：N-N/p1-N/p2-......-N/pi。但是会有质因数的倍数被重复去除，例如6即使质因数2的倍数，也是质因数3 的倍数，那么6就会先被2去除，再被3去除。如下图：

浅蓝色的区域表示被去除两次，那么我们需要将其加回来则上述变为：N-N/p1-N/p2-......-N/pi+N/(p1*p2)+N/(p2*p3)+N/(p1*p3)+......+N/(pi*pj)。

这个时候问题又来了深色的区域又被加了三次，那么则需要将其减去，同样的如果是多个质因数的倍数被多次减去，那么就会重复上面的错误
那么1~N中与N互质的个数即为：N-N/p1-N/p2-......+N/(p1*p2)+N/(p2*p3)+...-N/(p1*p2*p3)-......+1/(p1*p2*p3*p4)+.....
而这个推导的公式就等于
证毕。

理解了上述证明公式，那么求解相关问题就会非常简单

题目：873. 欧拉函数 - AcWing题库

代码：

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

using namespace std;

const int N=105;
int n,res[N];

void get_primes(int u)
{
    int cnt=0;
    //试除法求约数
    for(int i=2;i<=u/i;i++)
    {
        while(u%i==0)
        {
            u/=i;
            res[cnt]=i;
            cnt++;
            //以免多次储存。譬如8=2^3,如果不去重则会有：res[0]=2,res[1]=2,res[2]=2;
            if(u%i==0) cnt--;
        }
    }
    
    if(u>1) res[cnt]=u;
}

void euler(int a[],int u)
{
    //记得开long long
    int ans=u;
    for(int i=0;a[i]!=0;i++)
    {
//欧拉公式
        ans=ans/a[i]*(a[i]-1);
    }
    cout << ans << endl;
}

int main()
{
    cin >> n;
    for(int i=0;i<n;i++)
    {
        int x;
        cin >> x;
        get_primes(x);
        euler(res,x);
        //每次计算完成一个数，就将res重置，以免与后续冲突
        memset(res,0,sizeof res);
    }
    
    return 0;
}

题目：874. 筛法求欧拉函数 - AcWing题库

本题牵涉到两个公式的证明，在代码后会给出。和前面所学的线性筛，请及时回顾

代码：

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

using namespace std;

const int N=1e6+10;
int n,phi[N],primes[N],res;
bool st[N];

void get_eulers(int u)
{
//1特殊处理，当N等于1时，与1互质的个数为1
    phi[1]=1;
    for(int i=2;i<=u;i++)
    {
        if(!st[i])
        {
            primes[res++]=i;
//当数x是质数时，那么与x在1~x互质的个数为x-1，譬如2，3，5，7...
            phi[i]=i-1;
        }
        
        for(int j=0;primes[j] <= u/i;j++)
        {
//线性筛，筛去质数的倍数
            st[primes[j]*i]=true;
//公式一与公式二都是对被筛去的数 求欧拉数
            if(i%primes[j]==0)
            {
                phi[i*primes[j]]=primes[j]*phi[i];//公式一
                break;
            }

            phi[i*primes[j]]=(primes[j]-1)*phi[i];//公式二
        }
    }
    long long cnt=0;
    for(int i=1;i<=u;i++) cnt+=phi[i];
    cout << cnt;
}
int main()
{
    cin >> n;
    
    get_eulers(n);
    
    return 0;
}

公式一，若i%primes[j]==0，则有phi[i*primes[j]]=primes[j]*phi[i];这个因果关系的含义即为：
如果一个数x是N的质因数y的倍数，那么x*y的欧拉函数就为x*（y的欧拉函数）
证明：因为x%y==0，所以y是x的一个因数，又因为y是N的一个质因数（在筛质数的过程中是以质因数来筛的），那么y是x的质因数。根据算术基本定理 在这里，我们假设x=