Uva_11462 GCD - Extreme (II)
Uva_11462 GCD - Extreme (II)
若羽
发布于 2019-07-15 16:03:34
发布于 2019-07-15 16:03:34
题意：
给定一个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 <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 using namespace std;
16 #define LL long long
17 #define MAXN 4000010
18 #define MOD 1000000007
19 #define eps 1e-6
20 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 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-07-21 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读