[C++] NYOJ 570 解题报告

1
2
12

0
1
8

#include <stdio.h>
#include <math.h>
int Prime(long long n)
{
long long i,flag=0;
for(i=2;i<=(long long)sqrt(n);i++)
{
if(n%i==0)
{
flag=1;
break;
}
}
if(flag==0)
return 1;
else
return 0;
}
int main()
{
long long n,phi,flag,temp,i,j=0;
long long prime[4800]={0};
prime[j++]=2;
for(i=3;i<=46341;i+=2)
{
if(Prime(i)==1)
prime[j++]=i;
}
while((scanf("%lld",&n))!=EOF)
{
if(n==1)
printf("0\n");
else
{
temp=n;
phi=1;
i=0;
while(prime[i]!=0)
{
if(n==1)
break;
flag=0;
while(n%prime[i]==0)
{
flag=1;
phi=phi*prime[i];
n/=prime[i];
}
if(flag==1)
phi=(phi*(prime[i]-1))/prime[i];
i++;
}
if(n>1)
phi=phi*(n-1);
printf("%lld\n",temp-phi);
}
}
return 0;
}

#include<stdio.h>
int Eular(int  n){
   int i;
   int  ans=n;
   for(i=2;i*i<=n;++i){
      if(n%i==0){
        ans-=ans/i;
        while(n%i==0)
n=n/i;
        if(n==1)
break;
      }
   }
   if(n!=1)
 ans-=ans/n;
   return ans;
}
int main(){
  int i, j, k, n, x;
  while( ~scanf("%d",&n) ){
    int sum = 0;
    if(n==1){
      puts("0");
      continue;
    }
    for(i=1;i*i<=n;i++){
      if(n%i==0){
        sum+=(Eular(i));
        if( i!=1 && i*i!=n )
          sum+=(Eular(n/i));
      }
    }
    printf("%d\n",sum);
  }
  return 0;
}