15ecjtu校赛1006 （dfs容斥）

#include<bits/stdc++.h>
using namespace std;
int que[100010][20];
int jishu[100010];
void Init(){
    memset(jishu,0,sizeof(jishu));
    for(int i=2;i<=100000;i++)
    {
        if(jishu[i]) 
        continue;
        que[i][0]=i;
        jishu[i]=1;
        for(int j=2;j*i<=100000;j++)
         que[i*j][jishu[i*j]++]=i;
    }
}
__int64 dfs(int m,int n,int idx){
    __int64 ret=0;
    for(int i=idx;i<jishu[m];i++)
        ret+=n/que[m][i]-dfs(m,n/que[m][i],i+1);
    return ret;
}
int main()
{
    Init();
    int n;
    while(scanf("%d",&n)!=EOF)
{
        __int64 re=n;
        for(int i=2;i<=n;i++)
            re+=n-dfs(i,n,0);
        printf("%I64d\n",re);
    }
    return 0;
}