UVa 11426 - GCD - Extreme (II)

#数学 #gcd #phi

Published on 2016-02-29

描述

给定 $n(1 < n \le 4000000)$ ，请你计算下面式子的值：

\displaystyle\sum\limits_{i = 1}^{n-1}\sum\limits_{j = i + 1}^{n}\gcd(i, j)

样例输入

样例输出

67
13015
143295493160

分析

拿到式子，好像没思路。那就搞一搞和式，来个内外层交换：

\displaystyle\sum\limits_{i = 1}^{n-1}\sum\limits_{j = i + 1}^{n}\gcd(i, j) = \displaystyle\sum\limits_{j = 2}^{n}\sum\limits_{i = 1}^{j - 1}\gcd(i, j)

这样爽多了。我们把里层的这玩意设成 $f(n) = \sum\limits_{i = 1}^{n - 1}\gcd(i, n)$ ，这样就会固定一个参数 $n$ ，看起来可搞。
记 $g(i, n)$ 为满足 $\gcd(x, n) = i (1\le x\le n)$ 的 $x$ 个数，那么 $f(n) = \sum g(i, n) * i$ 。由于 $\gcd(x, n) = i(1\le x\le n)$ ，两边同时除去 $i$ ， $\gcd(\frac{x}{i}, \frac{n}{i}) = 1(1\le x\le n)$ ，即 $g(i, n) = \phi(\frac{n}{i})$ ，即与 $n$ 的最大公约数为 $i$ 的数个数即为与 $\frac{n}{i}$ 互素的数个数。
求 $f(n)$ 的过程变成了枚举 $n$ 的约数的过程，但约数很多，不好直接枚举。换一个思路，我们直接枚举约数，用类似筛法的过程去刷各个 $n$ ，刷的时候累加即可，复杂度 $O(n\log\log n)$ 。
本题的要点在于各种转换，是个不错的思维题。

代码

//  Created by Sengxian on 2/29/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  UVa 11426 gcd + phi + 思维
#include <algorithm>
#include <iostream>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#define br putchar('\n');
using namespace std;
inline int ReadInt() {
    int n = 0, ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}
const int maxn = 4000000 + 3;
long long phi[maxn], f[maxn], s[maxn];
void process() {
    memset(phi, 0, sizeof(phi));
    phi[1] = 1;
    for(int i = 2; i < maxn; ++i) if(!phi[i])
        for(int j = i; j < maxn; j += i) {
            if(!phi[j]) phi[j] = j;
            phi[j] = phi[j] / i * (i - 1);
        }
    memset(f, 0, sizeof(f));
    for(int i = 1; i < maxn; ++i)
        for(int j = i + i; j < maxn; j += i)
            f[j] += i * phi[j / i];
    s[0] = s[1] = 0;
    for(int i = 2; i < maxn; ++i)
        s[i] = s[i - 1] + f[i];
}

int main() {
    process();
    int n;
    while(n = ReadInt(), n)
        printf("%lld\n", s[n]);
    return 0;
}

附加输入

附加输出

2725
14208321806
8237287
8319160954
26343
376584743998
209185885
1365217
36535367082249
885271650
38
33221891524
906034
9601187847
37729
44509691503795
1
29401976509
144732617
21686
5114484
20
43782
32574957
5534028
42421
723868691
5237427576
71887733425828
230227
37000
1958618608264
15341
312593179
2997908
7091734021
3544968
149396
23608437
234613937007
172
240197159
18496
10463800744
43782
1255629
528897503942
1040608982
43782
129325
17855

模运算总结 UVa 10312 - Expression Bracketing

Sengxian's Blog