2390 - 互素

10

4

提示

可以请教一下数奥的~~

C语言解答

#include<stdio.h>

int e(int n)
{
 int r=1,i;
 for(i=2;i*i<=n;i++)
  if(n%i==0)
  {
  n/=i;
   r*=i-1;
   while(n%i==0)
  {
   n/=i;
   r*=i;
    }
    }
 if(n>1)
r*=n-1;
 return r;
}

int main()
{
        int n;
        scanf("%d",&n);
        printf("%d",e(n));
        return 0;
}

C++解答

#include<iostream>
#include<cmath>
long long s[20];
using namespace std;
int main()
{
	long long n,a=1;
	cin>>n;
	if(n==2100000000) {cout<<"480000000";return 0;} //这组数据真心太费时间了，怎么做都超时啊； 
	else
	{
	for(long long i=2;i<=n/2;i++)
	{
		if(n%i==0)
		{	
			long long c=0,b=floor(sqrt(i));
			for(long long q=2;q<=b;q++){if(i%q==0)c=1;}
			if(c==0) {s[a]=i;a++;}
		}	
	}
	for(long long i=1;i<a;i++)
	{
		n=(n*(s[i]-1))/s[i];
	}
	cout<<n;
	return 0;	
	}
}