GCD Again HDU - 1787 （欧拉函数 or 容斥原理）

240Sample Output
01
欧拉函数
#include <iostream>#include <cstdio>#include <cmath>#include <queue>#include <stack>#include <map>#include <algorithm>#include <vector>#include <string>#include <cstring>#include <sstream>#define INF 100000000using namespace std;int n;const int size=1000000;int vis[1000000];int solve(){    int ans=1;    int tmp=int(sqrt(n)+0.5);    for(int i=2;i<=tmp;i++)    {        if(n%i==0)        {            n/=i;            ans*=(i-1);        }        while(n%i==0)        {            n/=i;            ans*=i;        }    }    if(n>1)    {        ans*=n-1;    }    return ans;}int main(){    while(scanf("%d",&n)==1)    {        int a=n;        if(n==0) return 0;        int cnt=0;        int ans=solve();        ans=a-1-ans;        printf("%d/n",ans);    }    return 0;}
容斥原理
#include <iostream>#include <cstdio>#include <cmath>#include <queue>#include <stack>#include <map>#include <algorithm>#include <vector>#include <string>#include <cstring>#include <sstream>#define INF 100000000using namespace std;int n;int j;int p[10000];int s;void solve(int cur,int m,int k){    if(cur==j)    {        if(m==1) return;        if(k%2==1) s+=n/m-1;        else s-=n/m-1;    }    else    {        solve(cur+1,m,k);        solve(cur+1,m*p[cur],k+1);    }}int main(){    while(scanf("%d",&n)==1)    {        if(n==0) return 0;        j=0;        int nn=n;        for(int i=2;i*i<=nn;i++)        {            if(nn%i==0)            {                p[j++]=i;                while(nn%i==0)                {                    nn/=i;                }            }        }        if(nn>1)        {            p[j++]=nn;        }        s=0;        solve(0,1,0);        printf("%d/n",s);    }    return 0;}