欧拉函数

定义：若则称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欧拉函数的值。