题目链接：https://ac.nowcoder.com/acm/problem/212919

到主站看：https://blog.csdn.net/weixin_43346722/article/details/109270456

题目

牛半仙有 个妹子，每个妹子有一个属性值，第 个妹子的属性值为 。
牛半仙认为 个妹子 的相同度为 。
牛半仙想知道 的值。

输入

一行一个整数 。

输出

一行一个整数，表示任意三个妹子的相同度之和。

样例输入

2

样例输出

9

数据范围

对于 的数据，
对于 的数据，
表示 的最大公约数。

思路

这道题有很多种做法，我选择了最简单的预处理（因为只会这个
还有莫比乌斯反演和欧拉两种做法。

预处理的主要思想就是先预处理出 gcd 中一边是 ，另一边从 枚举到 的 ，我们就是预处理数所有 的和。

那与处理完之后，我们就可以枚举题目的 跟 ，因为前面预处理了，就可以省去枚举 的部分。

时间复杂度是 ，勉强能过。

比赛时

想了一会就想到了预处理的方法。

在看了一下复杂度应该可行就打完跑了。

代码

#include<cstdio>

using namespace std;

int n, a[1001], ans;

int gcd(int x, int y) {
    if (!y) return x;
    return gcd(y, x % y);
}

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

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            a[i] += gcd(i, j);//预处理出一对

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            ans += a[gcd(i, j)];//统计

    printf("%d", ans);

    return 0;
}