牛半仙的妹子gcd

题目描述

牛半仙有 $n$ 个妹子，第 $i$ 个妹子的属性值为 $a_i = n - i + 1$ （属性值序列为 $(n, n-1, \ldots, 1)$ ）。定义 $k$ 个妹子 $\{b_1, \ldots, b_k\}$ 的相同度为 $\gcd(a_{b_1}, \ldots, a_{b_k})$ ，求 $\sum_{i=1}^{n} \sum_{j=1}^{n} \sum_{k=1}^{n} \gcd(i, j, k)$ （下标可重复，即全部 $n^3$ 个有序三元组）的值。

输入：一行一个正整数 $n$ （40% 的数据 $n \leqslant 200$ ，100% 的数据 $n \leqslant 1000$ ）。输出：一行一个整数表示相同度之和。样例输入 2，样例输出 9：8 个有序三元组中只有 $(2,2,2)$ 的 gcd 为 2，其余 7 个都含 1、gcd 为 1，故 $7 \times 1 + 2 = 9$ 。

思路

属性值序列是 $1..n$ 的一个排列，故答案就是 $\sum_{i,j,k=1}^{n} \gcd(i,j,k)$ 。由 gcd 结合律 $\gcd(i,j,k) = \gcd(\gcd(i,j), k)$ ，按 $g = \gcd(i,j)$ 把全部数对分进互不相交的桶： $cnt[g]$ 为前两数 gcd 恰为 $g$ 的数对个数， $S(g) = \sum_{k=1}^{n} \gcd(g,k)$ ，答案为 $\sum_g cnt[g] \cdot S(g)$ ； $cnt$ 和 $S$ 各用一次 $O(n^2)$ 枚举求得， $n \leqslant 1000$ 轻松通过，注意答案超过 $2^{30}$ 要用 64 位整数。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 17:39
# update_at: 2026-10-04 14:55

import sys
from math import gcd


def pair_gcd_counts(n: int) -> list[int]:
    """cnt[g] = 1 ≤ i, j ≤ n 中 gcd(i, j) 恰好等于 g 的数对个数。"""
    cnt = [0] * (n + 1)
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            cnt[gcd(i, j)] += 1
    return cnt


def third_gcd_sum(g: int, n: int) -> int:
    """固定前两数的 gcd 为 g 时，第三个数 k 的贡献和：Σ gcd(g, k)。"""
    return sum(gcd(g, k) for k in range(1, n + 1))


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)  # 题面唯一的位置量：妹子个数 n
    cnt = pair_gcd_counts(n)

    # gcd(i, j, k) = gcd(gcd(i, j), k)：先按前两数的 gcd 分组，组内第三数的贡献相同
    ans = sum(c * third_gcd_sum(g, n) for g, c in enumerate(cnt) if c)
    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-04 21:49
 * update_at: 2026-10-04 21:49
 */

// 牛半仙的妹子gcd：求 sum_{i,j,k=1}^{n} gcd(i, j, k)
// 属性值序列 (n, n-1, ..., 1) 是 1..n 的排列，所以答案就是上述三重 gcd 和。
#include <cstdio>

typedef long long ll;

const int MAXN = 1005;

int n;
ll cnt[MAXN]; // cnt[g] = 1 <= i, j <= n 中 gcd(i, j) 恰好等于 g 的数对个数
ll sum[MAXN]; // sum[g] = 第三个数 k 取 1..n 时 gcd(g, k) 的和

// 求 a, b 的最大公约数
ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    scanf("%d", &n);

    // 第一段：枚举全部数对 (i, j)，按前两数的 gcd 分桶计数
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cnt[gcd(i, j)]++;

    // 第二段：gcd(i,j,k) = gcd(gcd(i,j), k)，对每个 g 求第三维的贡献和 S(g)
    for (int g = 1; g <= n; g++)
        for (int k = 1; k <= n; k++)
            sum[g] += gcd(g, k);

    // 结算：每个数对 (i,j) 落在唯一的桶 cnt[gcd(i,j)] 里，贡献是 sum[gcd(i,j)]
    ll ans = 0;
    for (int g = 1; g <= n; g++)
        ans += cnt[g] * sum[g];

    printf("%lld\n", ans);
    return 0;
}

目录

题目描述

思路

参考代码