HDU 2824

发布时间:2016-12-9 23:29:55 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU 2824",主要涉及到HDU 2824方面的内容,对于HDU 2824感兴趣的同学可以参考一下。

        这还是与欧拉函数有关的,不过这次不是求一个,而是求多个,所以我们不能一个一个用求单个数的欧拉函数值的方法,需要用筛法求多个连续数的欧拉函数值。         如果你没有看过筛法求素数,那么建议先看一下筛法求素数,这将有助于理解这道题的算法思想。         后面给出的代码,会算出从2~n所有数的欧拉函数值,我们只需截取a~b范围内的欧拉函数值相加即可。         首先,需要声明一个数组,并需要全部初始化为0。然后从2~n中找出素数,让后找到素因子含该素数的所有数(当然是在n内),乘以(1-1/p),如此循环。其中需要处理一些细节,各位在看完代码后应该就能明白。最后提示一个细节,就是保存总数的变量类型应该为long long型。 代码(G++): #include <cstdlib> #include <iostream> using namespace std; int array[3000000]; int main(int argc, char *argv[]) { int a,b,i,j; long long count; memset(array,0,sizeof(array)); for(i=2;i<3000000;i++) { if(!array[i]) { for(j=i;j<3000000;j+=i) { if(!array[j]) array[j]=j; array[j]=array[j]/i*(i-1); } } } while(cin>>a>>b) { count=0; for(i=a;i<=b;i++) count+=array[i]; cout<<count<<endl; } system("PAUSE"); return EXIT_SUCCESS; } 附上原题: The Euler function                                                                         Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) 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

上一篇:C语言结构体的大小——内存对齐和位域的使用
下一篇:cocos2d-x中的缓存CCTextureCache、CCSPriteFrameCache、CCAnimationCache

相关文章

关键词: HDU 2824

相关评论