欧拉函数

源代码：

#include<cstdio>
#include<cmath>
#define LL long long
using namespace std;
LL n,Ans=1,Num(0),Sum[3500]={0},Prime[3500];
bool Flag[32000]={0};
void Euler() //欧拉筛法。
{
    LL t=sqrt(n)+1;
    for (LL a=2;a<=t;a++)
    {
        if (!Flag[a])
          Prime[Num++]=a;
        for (LL b=0;b<Num&&a*Prime[b]<=t;b++)
        {
            Flag[a*Prime[b]]=true;
            if (!(a%Prime[b]))
              break;
        }
    }
}
LL Count(LL X,LL S) //快速幂。
{
    LL T=1;
    while (S)
    {
        if (S&1)
          T*=X;
        X*=X;
        S>>=1;
    }
    return T;
}
int main()
{
    scanf("%lld",&n);
    Euler();
    for (LL a=0;a<Num;a++)
    {
        if (!n)
          break;
        while (!(n%Prime[a])&&n) //分解质因数。
        {
            Sum[a]++;
            n/=Prime[a];
        }
    }
    if (n>1)
      Ans=n-1;
    for (LL a=0;a<Num;a++)
      if (Sum[a])
        Ans*=(Prime[a]-1)*Count(Prime[a],Sum[a]-1);
    printf("%lld",Ans);
    return 0;
}

/*
    利用欧拉函数的以下性质求解即可：
        (1)φ(n)=φ(p^k)=p^k-p^(k-1)=(p-1)p^(k-1)，p为质数；
        (2)φ(mn)=φ(m)*φ(n)，m和n互质；
    数论耳。
*/