欧拉函数

定义：若则称a，b互质。gcd(a,b,c)称为a，b，c互质，而称为两两互质。例如2,3,4互质但是不是两两互质。
欧拉函数
1~N中与N互质的数的个数被称为欧拉函数，记为。
欧拉函数的计算方法是对N分解

对N个数，排除以p为质因子的数，得到的就是欧拉函数。

int varphi(int n){
    int ans=n;
    for(int i=2;i<=n/i;i++){
        if(n%i==0){
            ans = ans/i*(i-1);
            while(n%i==0&&n!=0)n/=i;
        }
    }
    if(n>1)ans = ans/n*(n-1);
    return ans;
}

欧拉函数的性质

性质1：，1~n中与n互质的数的和为
性质2：若a,b互质，则
证明性质1：gcd(n,x) = gcd(n,n-x),所以与n互质的数是成对出现的分别为x和n-x平均值是一共有个。
证明性质2：根据求欧拉函数的公式，直接带入等式。等式左右两边相等。
下面这个定义是积性函数的定义。
定义：如果当a，b互质时，有f(ab) = f(a)*f(b),那么称函数f为积性函数。
性质3欧拉函数满足，积性函数也满足。
性质3：若f是积性函数，且在算数基本定理中，则
性质4：设p为质数，若且则
性质5：设p为质数，若但则
性质6：
证明：首先看性质3直接代入求欧拉函数的公式即可，等式两边相等。
性质4，n/p包含质数p，n与n/p的质因数集合相同。求欧拉函数的公式中，只有N不同。从而可以推出关系。
性质5，n/p不包含质数p，n包含质数p。求欧拉函数的公式中，N不同，并且n/p比n少乘了一个
性质6：首先证明是积性函数。令f代表这个公式。

n与m互质，证明了f是积性函数。对于单个因此来说，
因此对于整个n分解为几个然后使用积性函数性质求出f(n)。

利用埃筛计算欧拉函数的公式

埃筛会将每个合数被他不同的质因数筛一次。例如12被2和3筛。而欧拉函数需要被每个不同质因数p，乘一次。修改代码的筛法，从标记合数，变为对欧拉函数执行乘法。
有更好用的线筛，埃筛一般用不到。

利用线筛计算欧拉函数

线筛每个数只会被他的最小质因数筛一次。考虑i如果说明p不是i最小的质因数，根据性质5 phi[i*p] = phi[i]*(p-1)。如果说明p是i最小的质因数，phi[i*p]=phi[i]*p

bool v[100010];
int phi[100010];
vector<int> a;
void euler(int n){
    phi[1]=1;
    for(int i = 2;i<=n;i++){
        if(v[i]==0)a.push_back(i),phi[i]=i-1;
        for(int j = 0;i*a[j]<=n;j++){
            phi[i*a[j]] = phi[i]*(a[j]-1);
            v[i*a[j]]=1;
            if(i%a[j]==0){
                phi[i*a[j]] = phi[i]*a[j];
                break;
            }
        }
    }
}

总结

求欧拉函数可以使用试除法求出N的每个质因数，顺便求出N的欧拉函数值。
使用线筛的时间求出1~N欧拉函数的值。