[POJ2478]Farey Sequence-白红宇

[POJ2478]Farey Sequence

阅读量：4322 次

发布时间：2019-06-06

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

题目链接：http://poj.org/problem?id=2478

好水的题啊，求欧拉函数前n项和，注意是从2开始。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
            7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 13 using namespace std;14 15 typedef long long LL;16 const int maxn = 1e6+1;17 LL phi[maxn];18 19 void geteular() {20 memset(phi, 0, sizeof(phi));21 phi[1] = 1;22 for(int i = 2; i < maxn; i++) {23 if(!phi[i]) {24 for(int j = i; j < maxn; j+=i) {25 if(!phi[j]) {26 phi[j] = j;27 }28 phi[j] = phi[j] / i * (i - 1);29 }30 }31 }32 }33 int main() {34 geteular();35 int n;36 while(~scanf("%d", &n) && n) {37 LL sum = 0;38 for(int i = 2; i <= n; i++) {39 sum += phi[i];40 }41 printf("%I64d\n", sum);42 }43 }