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
题解:
求一个欧拉函数的和,求法参见这篇博客.
1 #include <algorithm> 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 using namespace std; 8 typedef long long ll; 9 const int N=3000005,M=300005; 10 bool d[N];int l,r,phi[N],prime[M],m=0; 11 void work(){ 12 int tmp; 13 phi[1]=1; 14 for(int i=2;i<N;i++){ 15 if(!d[i]){ 16 phi[i]=i-1; 17 prime[++m]=i; 18 } 19 for(int j=1;j<=m && i*prime[j]<N;j++){ 20 tmp=i*prime[j]; 21 d[tmp]=true; 22 if(i%prime[j]){ 23 phi[tmp]=phi[i]*(prime[j]-1); 24 } 25 else{ 26 phi[tmp]=phi[i]*prime[j]; 27 break; 28 } 29 } 30 } 31 } 32 int main() 33 { 34 35 work(); 36 int a,b; 37 while(~scanf("%d%d",&a,&b)){ 38 long long sum=0; 39 for(int i=a;i<=b;i++) 40 sum+=phi[i]; 41 printf("%lld ",sum); 42 } 43 return 0; 44 }