欧拉函数学习笔记

欧拉函数几个性质

性质一：φ(n)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…(1-1/pn）

ll eulur(ll x){//根据定义求 ll ans=x; for(ll i=2;i*i<=x;i++){ if(x%i==0){ while(x%i==0) x/=i; ans=ans*(i-1)/i; } } if(x>1) ans=ans*(x-1)/x; return ans; }

性质二：所有小于n与n互质的数字的和sum=φ(n)/2*n其中互质的数都是成对出现，并且和为n

性质三：当n是奇数时候，φ(2*n)=φ(n);

性质四：如果i%p==0&&(i/p)%p==0 那么有φ(i)=φ(i/p)*p;else φ(i)=φ(i/p)*(p-1)

因此可以通过nlogn求出最小质因数，再O(n)预处理phi

int mindiv[N],phi[N]; void init(){ for(int i=1;i<N;++i) mindiv[i]=i; for(int i=2;i*i<N;i++){ if(mindiv[i]==i){ for(int j=i*i;j<N;j+=i){ mindiv[j]=i; } } } phi[1]=1; for(int i=2;i<N;i++){ phi[i]=phi[i/mindiv[i]]; if((i/mindiv[i])%mindiv[i]==0) phi[i]=phi[i]*mindiv[i]; else phi[i]=phi[i]*(mindiv[i]-1); } }

一个很好的blog:链接，讲了杜教筛，暂时不求甚解