欧拉函数求和
时间限制:1000 ms | 内存限制:65535 KB
难度:3
- 描述
-
题目描述很简单,求出
(PS:上面式子的意思是大于0小于n并且能整除n的所有d的欧拉函数值之和)。
- 输入
- 每行一个数n(n<2^31),输入以文件结尾结束。
- 输出
- 每个结果占一行。
- 样例输入
-
1 2 12
- 样例输出
-
0 1 8
- 来源
- rihkddd原创
-
上传者
思路:求n所有因子(除n)的欧拉函数值的和 枚举n的因子,并求其和(建议把我今天晚上写的入门全看一遍
就基本理解了(_ _))/*在数论,对正整数n,欧拉函数是少于或等于n的数中与n互质的数的数目。*/ /*思路:枚举n的因子。 假设n的因子为d。d*gcd(x/d,n/d)=1。 d*Euler(n/d)就是因子为gcd(x,n)=d,从而求gcd(x,n)的和。*/ #include<stdio.h> #include<string.h> #include<iostream> using namespace std; long long Euler(long long n)//欧拉函数 { long long c=n,i; for(i=2; i*i<=n; i++) { if(n%i==0) { while(n%i==0) n/=i; c=c/i*(i-1);//φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn); } } if(n!=1) c=c/n*(n-1); return c; } int main() { long long a; int t; while(cin>>a) { long long c=0,i; for(i=1; i*i<=a; i++) { if(a%i==0) { if(i!=a) c+=Euler(i); if(i*i!=a&&i!=1) c+=Euler(a/i); } } cout<<c<<endl; } }