首页 > 代码库 > HDU——T 2824 The Euler function
HDU——T 2824 The Euler function
http://acm.hdu.edu.cn/showproblem.php?pid=2824
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7752 Accepted Submission(s): 3217
Problem Description
The Euler function phi is an important kind of function in number theory, (n) represents the amount of the numbers which are smaller than n and coprime to n, and this function has a lot of beautiful characteristics. Here comes a very easy question: suppose you are given a, b, try to calculate (a)+ (a+1)+....+ (b)
Input
There are several test cases. Each line has two integers a, b (2<a<b<3000000).
Output
Output the result of (a)+ (a+1)+....+ (b)
Sample Input
3 100
Sample Output
3042
Source
2009 Multi-University Training Contest 1 - Host by TJU
欧拉函数表。前缀和
1 #include <algorithm> 2 #include <cstdio> 3 4 using namespace std; 5 6 #define LL long long 7 const int N(3000233); 8 LL a,b,phi[N]; 9 10 void All_phi()11 {12 for(int i=1;i<=N;i++)13 phi[i]=i;14 for(int i=2;i<=N;i++)15 if(phi[i]==i)16 for(int j=i;j<=N;j+=i)17 phi[j]=phi[j]/i*(i-1);18 }19 20 int main()21 {22 All_phi();23 for(int i=1;i<=N+1;i++) phi[i]=phi[i-1]+phi[i];24 for(;scanf("%d%d",&a,&b)!=EOF;)25 printf("%I64d\n",phi[b]-phi[a-1]);26 return 0;27 }
HDU——T 2824 The Euler function
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。