题目地址
题解
先讨论任何没有限制的情况
\[\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}
}
\]
\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}
\]
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;
}