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 } 

 

Database error: [Table 'ac_search_cache' is marked as crashed and should be repaired]

SELECT * FROM ac_search_cache WHERE hash = '9c2aa86aa7c2ea9c924a7c6ec573f7f984fd5033' LIMIT 1;