首页 > 代码库 > HDU 2824 The Euler function

HDU 2824 The Euler function

The Euler function

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3789    Accepted Submission(s): 1569


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
 
 
线性筛选欧拉函数
 
#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>#include <iostream>using namespace std;const int N = 3000010;long long  phi[N];void solve(){    memset( phi , 0 ,sizeof phi );    phi[1] = 1 ;    for( int i = 2 ; i < N ; ++i ){        if( !phi[i] ){            for( int j = i ; j < N ; j += i ){                if( !phi[j] ) phi[j] = j ;                phi[j] = phi[j] / i * ( i - 1 );            }        }    }}int main(){    ios::sync_with_stdio(false);    solve();    for( int i = 2 ; i < N ; ++i ){        phi[i] += phi[i-1] ;    }    int a , b ;    while( cin >> a >> b  ){        cout << phi[b] - phi[ a - 1 ] <<endl;    }}

 

 

HDU 2824 The Euler function