The Euler function
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1937Accepted Submission(s): 794
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
Sample Output
3042
#include<stdio.h>
#include<math.h>
#define maxn 3000000
int phi[3000000+100];
void get_PHI()
{
int i,j;
for (i = 1; i <= maxn; i++) phi[i] = i;
for (i = 2; i <= maxn; i += 2) phi[i] /= 2;
for (i = 3; i <= maxn; i += 2) if(phi[i] == i)
{
for (j = i; j <= maxn; j += i)
phi[j] = phi[j] / i * (i - 1);
}
}
int main()
{
int a,b,i;
get_PHI();
while(scanf("%d%d",&a,&b)!=EOF)
{
__int64 sum=0;
for(i=a;i<=b;i++)
sum+=phi[i];
printf("%I64d\n",sum);
}
return 0;
}
//下面是爆内存的 但是有一点错误 值得 反省 所以也贴上
#include<stdio.h>
#include<math.h>
#define maxn 3000000
int phi[3000000+100];
__int64 sum[3000000+100];
void get_PHI()
{
int i,j;
for (i = 1; i <= maxn; i++) phi[i] = i;
for (i = 2; i <= maxn; i += 2) phi[i] /= 2;
for (i = 3; i <= maxn; i += 2) if(phi[i] == i)
{
for (j = i; j <= maxn; j += i)
phi[j] = phi[j] / i * (i - 1);
}
}
int main()
{
int a,b,i;
get_PHI();
sum[2]=phi[2];
for(i=3;i<=3000000;i++)
sum[i]=sum[i-1]+phi[i];
while(scanf("%d%d",&a,&b)!=EOF)
{
printf("%I64d\n",sum[b]-sum[a-1]);//注意这里 是a-1 以前也遇见过类似的情况
/*对于一串数相加后的sum 要特别注意下标应该是什么 千万特别留意下*/
}
return 0;
}
分享到:
相关推荐
hdu 1695 GCD(欧拉函数+容斥原理).docx
离线OJ题库(HDU ZJU等,部分有答案),需联网。
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了
(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数
收集的部分HDOJ杭电ACM题的代码 大牛勿下 全是基础供初级acmer使用
HDU的一题........HDU DP动态规
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1005.比较简单的一道题,有兴趣的可以看看。
HDU 动态规划(46道题目
100道 acm C语言 hdu 解题报告
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
我写的hdu上的一些题AC的题的代码 也许你会有用
hdu 1574 passed sorce
背包问题的模板,可以解决各类背包问题,根据问题需要修改参数即可。试用于ACM初学者。
For a positive integer n, let’s denote function f(n,m) as the m-th smallest integer x that x>n and gcd(x,n)=1. For example, f(5,1)=6 and f(5,5)=11. You are given the value of m and (f(n,m)?n)⊕n,...
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码