The Euler function(歐拉函數)

The Euler function

Time Limit : 2/1ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 39   Accepted Submission(s) : 19

Font: Times New Roman Verdana Georgia

Font Size: ← →

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<3).

Output

Output the result of (a)+ (a+1)+....+ (b)

Sample Input

3 100

Sample Output

3042
题解:打表水过;
代码:
 1 #include<stdio.h>
 2 #include<string.h>
 3 const int MAXN= 3010;
 4 __int64 dp[MAXN];
 5 int main(){
 6     memset(dp,0,sizeof(dp));
 7     dp[1]=1;
 8     for(int i=2;i<MAXN;i++){
 9         if(dp[i])continue;
10         for(int j=i;j<MAXN;j+=i){
11             if(!dp[j])dp[j]=j;
12             dp[j]=dp[j]/i*(i-1);
13         }
14     }
15     for(int i=2;i<MAXN;i++)dp[i]+=dp[i-1];
16     int a,b;
17     while(~scanf("%d%d",&a,&b))printf("%I64d\n",dp[b]-dp[a-1]);
18         return 0;
19 } 

 

更多相关文章
  • The Euler function Time Limit: 2/1 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submis
  • POJ2689 HDU2824 篩法、歐拉函數
    传送门什么的@百度.. Prime Distance Time Limit: 1MS Me
  • 找新朋友 Time Limit: 2/1 MS(Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s):6928    Accepted Submission(s): 3593 Problem Des
  • http://poj.org/problem?id=2478 http://acm.hdu.edu.cn/showproblem.php?pid=2824 欧拉函数模板裸题,有两种方法求出所有的欧拉函数,一是筛法,而是白书上的筛法. 首先看欧拉函数的性质: 欧拉函数是求小于n且和n互质(包括1)的正
  • Reflect(歐拉函數)
    Reflect Time Limit: 2/1 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 288    Accepted Submission(s): 174 Problem D ...
  • 此题中对时间有要求,如直接使用欧拉函数求解,每输入一个n,就得进行循环求出<n的每个数的欧拉函数, 这样会超时, 于是我们可预先将欧拉函数打表, 再进行一个循环加法运算,便可不超时得解. #include<iostr
  • 找新朋友 Time Limit: 2/1 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 9361    Accepted Submission(s): 4955 Problem De
  • poj3696       快速冪的優化+歐拉函數+gcd的優化+互質
    这题满满的黑科技orz 题意:给出L,要求求出最小的全部由8组成的数(eg: 8,88,,
一周排行