欧拉函数的几条重要性质

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define rg register ll
#define inf 2147483647
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define maxn 2000000
const double eps=1e-8;
using namespace std;
inline ll read()
{
    char ch=getchar();ll s=0,w=1;
    while(ch<48||ch>57){if(ch=='-')w=-1;ch=getchar();}
    while(ch>=48&&ch<=57){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}
    return s*w;
}
inline void write(ll x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+48);
}
ll n;
ll prime[maxn],visit[maxn],phi[maxn],tot;
inline void work()
{
    phi[1]=1;
    for(rg i=2;i<=n;i++)
    {
        if(!visit[i])
        {
            phi[i]=i-1;
            prime[++tot]=i;
        }
        for(rg j=1;j<=tot;j++)
        {
            ll k=prime[j]*i;
            if(k>maxn)break;
            visit[k]=1;
            if(i%prime[j]==0)
            {
                phi[k]=prime[j]*phi[i];
            }
            else  phi[k]=phi[i]*(j-1);
        }
    }
    cout<<phi[n]<<endl;
}
int main()
{
    n=read();
    work();
    return 0;
}