首页 > ACM题库 > HDU-杭电 > HDU 2824-The Euler function-最小生成树-[解题报告]HOJ
2014
02-17

HDU 2824-The Euler function-最小生成树-[解题报告]HOJ

The Euler function

问题描述 :

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)

输入:

There are several test cases. Each line has two integers a, b (2<a<b<3000000).

输出:

There are several test cases. Each line has two integers a, b (2<a<b<3000000).

样例输入:

3 100

样例输出:

3042

 

#include<stdio.h>
#include<stdlib.h>
__int64  num[3000024];
int prime[220000];
bool isprime[3000024]={0};
void eular()
{
	int count=0;
	__int64 k;
	for( int i=2; i<=3000000; i++ )
	{       
		if( !isprime[i] )
		{
			prime[++count]=i;
			num[i]=i-1;
		}
		for( int j=1; j<=count&&( (k=prime[j]*i)<=3000000 );j++  )
		{
			isprime[k]=1;
			if( i%prime[j]==0 )
			{
				num[k]=num[i]*prime[j];
			}
			else num[k]=num[i]*( prime[j]-1 );
		}
	}
}
int main( )
{
	int n,m,i;
	eular();//结果存储在num[]中
	for(i = 3;i <=3000000;i++)
		num[i] = num[i-1] + num[i];
	while( scanf( "%d%d",&n,&m )!=EOF )
		printf( "%I64d\n",num[m]-num[n-1] );
	return 0;
}

解题参考:http://blog.csdn.net/mishifangxiangdefeng/article/details/7109185


  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  4. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  5. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

  6. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish