# 欧拉函数详解

2018-01-27 11:14:32来源:cnblogs.com作者:自为风月马前卒人点击

## 性质

1.\$/phi(n)\$为积性函数

2.\$/sum_{d|n}/phi(d)=n\$

3.\$1\$到\$n\$中与\$n\$互质的数的和为\$n*/dfrac{/phi(n)}{2}(n>1)\$

## 计算方法

### \$/sqrt(n)\$计算单值欧拉函数

(仅有\$n\$与\$n\$不互质)

#### 3.当\$n\$为合数时

\$\$/phi(n)\$\$

\$\$=/varphi /left( a^{p_{1}}_{1}a^{p_{2}/ldots }_{2}a^{Pk}_{k}/right)\$\$

\$\$=/prod ^{k}_{i=1}a^{P_i}-a^{P_{i}-1}_{i}\$\$

\$\$=/prod ^{k}_{i=1}a^{Pi}_{i}(1-/dfrac {1}{p_{i}})\$\$

\$\$=n*/prod ^{k}_{i=1}(1-/dfrac {1}{p_{i}})\$\$

`#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#define LL long long using namespace std;int main(){    LL N;    while(cin>>N&&N!=0)    {        int limit=sqrt(N),ans=N;        for(int i = 2; i <= limit ; ++i)        {            if(N%i==0) ans=ans/i*(i-1);            while(N%i==0) N=N/i;        }        if(N>1) ans=ans/N*(N-1);        printf("%d/n",ans);    }    return 0;}`

### 线性筛

#### 性质2

\$=/varphi /left( i/ast p/right) =/varphi /left( i/right) /ast /left( p-1/right)\$

#### 性质3

http://blog.csdn.net/Lytning/article/details/24432651

`#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#define LL long long using namespace std;const int MAXN=1e6+10;int prime[MAXN],tot=0,vis[MAXN],phi[MAXN],N=10000;void GetPhi(){    for(int i=2;i<=N;i++)    {        if(!vis[i])        {            prime[++tot]=i;            phi[i]=i-1;        }        for(int j=1;j<=tot&&prime[j]*i<=N;j++)        {            vis[ i*prime[j] ] = 1;             if(i%prime[j]==0)            {                phi[ i*prime[j] ]=phi[i]*prime[j];                break;            }            else phi[ i*prime[j] ]=phi[i]*(prime[j]-1);        }    }}int main(){    GetPhi();    cin>>N;    printf("%d/n",phi[N]);    return 0;}`

## 例题

http://poj.org/problem?id=2407

http://poj.org/problem?id=2478