题目地址

题目链接

题解

先讨论任何没有限制的情况
\[ \large { \begin{aligned} &\sum_{i=1}^{n}\sum_{j=1}^{n}gcd(i,j)\\ &=\sum_{k=1}^{n}k\sum_{i=1}^{n}\sum_{j=1}^{n}[gcd(i,j)=k]\\ &=\sum_{k=1}^{n}k\sum_{i=1}^{\lfloor \frac{n}{k}\rfloor }\sum_{j=1}^{\lfloor \frac{n}{k}\rfloor }[gcd(i,j)=1]\\ &=\sum_{k=1}^{n}k\sum_{i=1}^{\lfloor \frac{n}{k}\rfloor }\sum_{j=1}^{\lfloor \frac{n}{k}\rfloor }\sum_{d|gcd(i,j)}\mu(d)\\ &=\sum_{k=1}^{n}k\sum_{d=1}^{n}{\mu(d)\lfloor \frac{n}{kd}\rfloor^2} \end{aligned} } \]

因为这个公式里面，我们对于所有的(i,j)，同时也算了(j,i)

显然gcd(i,j)=gcd(j,i)

所以只需要除以2即可

但是因为对于所有的(i,i)。我们只算了一次，因为这个在答案中不算进去，所以我们可以直接减掉再除以2

所以最后的答案
\[ \large ANS= \frac{\sum_{k=1}^{n}k\sum_{d=1}^{n}{\mu(d)\lfloor \frac{n}{kd}\rfloor^2}-\sum_{i=1}^{n}i}{2} \]
用容斥的思想来理解就很简单了

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define N 501
int n;
int vis[N], p[N], cnt = 0, mu[N], sum[N];

void init() {
    mu[1] = sum[1] = 1;
    for(int i = 2; i < N; ++i) {
        if(!vis[i]) {p[++cnt] = i; mu[i] = -1;}
        for(int j = 1; j <= cnt && p[j] * i < N; ++j) {
            vis[p[j] * i] = 1;
            if(i % p[j] == 0) break;
            mu[i * p[j]] -= mu[i];
        }
        sum[i] = sum[i - 1] + mu[i];
    }
}

int calc(int m, int k) {
    int ans = 0;
    for(int l = 1, r; l <= m; l = r + 1) {
        r = m / (m / l);
        ans += (n / l / k) * (n / l / k) * (sum[r] - sum[l - 1]);
    }
    return ans;
}

int main() {
    init();
    while(scanf("%d", &n) == 1 && n) {
        int ans = 0;
        for(int i = 1; i <= n; ++i) {
            ans += i * calc(n, i);
        }
        printf("%d\n", (ans - (n * (n + 1)) / 2) / 2);
    }
    return 0;
}

优质内容筛选与推荐>>
1、交互设计师必看：怎样让你的线框图发挥出真正价值？
2、从零开始折腾博客(5)：全站从http升级到https
3、数据科学家修炼指南
4、python3-socket验证客户端连接的合法性,下载进度条的实现
5、关于安卓开发选项卡的实现

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。

阅读

已发送

发送中