HDU 2824 The Euler function 欧拉函数-白红宇

HDU 2824 The Euler function 欧拉函数

阅读量：6815 次

发布时间：2019-06-26

本文共 1147 字，大约阅读时间需要 3 分钟。

　　题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=2824

　　题目描述：求欧拉函数？

　　解题思路：欧拉函数

　　代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #define lson l, m, rt<<1#define rson m+1, r, rt<<1|1#define mem0(a) memset(a,0,sizeof(a))#define sca(x) scanf("%d",&x)#define de printf("=======\n")typedef long long ll;using namespace std;const int maxn = 3e6+10;const int n = 3e6;int phi[maxn];void init() { for( int i = 2; i <= n; i++ ) { phi[i] = 0; } 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); } } }// for( int i = 1; i <= 10; i++ ) {// cout << phi[i] << " ";// }// cout << endl;}int main() { init(); int a, b; while( scanf( "%d%d", &a, &b ) == 2 ) { ll ans = 0; for( int i = a; i <= b; i++ ) { ans += phi[i]; } printf( "%lld\n", ans ); } return 0;}