Uva_11462 GCD - Extreme (II)-白红宇

Uva_11462 GCD - Extreme (II)

阅读量：5115 次

发布时间：2019-06-13

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

题意：

　　给定一个n，求：GCD(1, 2) + GCD(1, 3) + GCD(2, 3) + …… + GCD(1, n) + GCD(2, n) + …… + GCD(n-1, n);

设f(n) = ΣGCD(i, n), i = 1, 2, 3, ... , n-1

　　本题即求：f(2) + f(3) + f(4) + ... + f(n)

　　设s(n) = f(2) + f(3) + f(4) + ... + f(n)

　　1）

　　令 d = GCD(x, n), d 是 x, n的约数

　　所以， 1 = GCD(x/d, n/d) 所有满足条件的 x/d 的个数则为 n/d的欧拉函数值phi(n/d);

　　即满足d = GCD(x, n) 的x的个数为phi(n/d) , 这部分的和为phi(n/d) * d;

　　得， f(n) = Σ (i * phi(n/i)) i = [1, n-1]区间内n的所有约数。

　　2）

　　得出f(n) 的值，我们就可以递推出s(n)的值了， s(n) = s(n-1) + f(n) , n >= 3

　　代码如下：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
             8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #include 
                 
                  13 #include 
                  
                   14 #include 
                   
                    15 using namespace std;16 #define LL long long17 #define MAXN 400001018 #define MOD 100000000719 #define eps 1e-620 int n;21 LL f[MAXN], s[MAXN];22 int phi[MAXN];23 int euler_phi(int n)24 {25 int m = (int)sqrt(n + 0.5);26 int ans = n;27 for(int i = 2; i <= m; i ++)28 if(n % i == 0)29 {30 ans = ans / i * (i - 1);31 while(n % i == 0) n /= i;32 }33 if(n > 1) ans = ans / n * (n - 1);34 return ans;35 }36 37 void phi_table(int n)38 {39 for(int i = 0; i <= n; i ++) phi[i] = 0;40 phi[1] = 1;41 for(int i = 2; i <= n; i ++)42 if(!phi[i])43 {44 for(int j = i; j <= n; j += i)45 {46 if(!phi[j]) phi[j] = j;47 phi[j] = phi[j] / i * (i - 1);48 }49 }50 }51 void init()52 {53 for(int i = 1; i < MAXN; i ++)54 for(int j = 2 * i; j < MAXN; j += i)55 f[j] += i * phi[j/i];56 s[2] = f[2];57 for(int i = 3; i < MAXN; i ++)58 s[i] = s[i-1] + f[i];59 }60 61 int main()62 {63 phi_table(MAXN - 5);64 init();65 while(scanf("%d", &n) && n)66 {67 printf("%lld\n", s[n]);68 }69 return 0;70 }