NYOJ 570 解题报告
欧拉函数求和
时间限制： 1000 ms | 内存限制： 65535 KB
难度： 3
描述 题目描述很简单，求出
（PS:上面式子的意思是大于0小于n并且能整除n的所有d的欧拉函数值之和）。
输入 每行一个数n（n<2^31)，输入以文件结尾结束。 输出 每个结果占一行。 样例输入 1
2
12
样例输出 0
1
8 这道题又是一道关于数论的题目。首先，我们需要知道，欧拉函数的和函数为，其中d包含1至n（含1和n），这和题目中的“和函数”不含有n是不同的。所以，。这里又要知道欧拉phi函数的计算公式，
知道了这两个式子，这道题就没什么了~~~
附上我的代码。
#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={0};
prime=2;
for(i=3;i<=46341;i+=2)
{
if(Prime(i)==1)
prime=i;
}
while((scanf("%lld",&n))!=EOF)
{
if(n==1)
printf("0\n");
else
{
temp=n;
phi=1;
i=0;
while(prime!=0)
{
if(n==1)
break;
flag=0;
while(n%prime==0)
{
flag=1;
phi=phi*prime;
n/=prime;
}
if(flag==1)
phi=(phi*(prime-1))/prime;
i++;
}
if(n>1)
phi=phi*(n-1);
printf("%lld\n",temp-phi);
}
}
return 0;
}
标程里是直接硬算，从头遍历到尾。其实知道了第一个公式就不用这样了！
#include<stdio.h>
int Eular(intn){
int i;
intans=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;
}
文档来源：51CTO技术博客https://blog.51cto.com/liulizhi1996/3035752
页:
[1]