题目大意
求
\[\sum_{a>0,b>0,c>0,a+b+c=n}\mathrm{lcm}(c,\gcd(a,b)) \]\((3\leq n\leq 10^5)\)
题解
\[ans=\sum_{a}\sum_{b} \mathrm{lcm}(n-a-b,\gcd(a,b))\\ =\sum_{d=1}^n\sum_{a}\sum_{b}\mathrm{lcm}(n-a-b,d)[\gcd(a,b)=d]\\ =\sum_{d=1}^n\sum_{x=1}^{\lfloor\frac{n-1}{d}\rfloor}\sum_{p=1}^{x-1}\mathrm{lcm}(n-xd,d)[\gcd(p,x-p)=1]\\ =\sum_{d=1}^n\sum_{x=1}^{\lfloor\frac{n-1}{d}\rfloor}\mathrm{lcm}(n-xd,d)\sum_{p=1}^{x-1}[\gcd(p,x-p)=1] \]令 \(f(n)=\sum_{i=1}^{n-1}[\gcd(i,n-i)=1]\)，
\[f(n)=\sum_{i=1}^{n-1}[\gcd(i,n-i)=1]\\ =\sum_{i=1}^{n-1}\sum_{c|\gcd(i,n-i)}\mu(c)\\ =\sum_{c=1}^{n-1}\mu(c)\sum_{i=1}^{n-1}[c|\gcd(i,n-i)]\\ =\sum_{c|n}\mu(c)\left(\left\lfloor\frac{n}{c}\right\rfloor-1\right) \]所以可以在 \(O(n\sqrt n)\) 的时间内求出全体 \(f(1)\sim f(n)\) 。
\[ans=\sum_{d=1}^n\sum_{x=1}^{\lfloor\frac{n-1}{d}\rfloor}\mathrm{lcm}(n-xd,d)f(x)\\ =\sum_{x=1}^n\sum_{d=1}^{\lfloor\frac{n-1}{x}\rfloor}\mathrm{lcm}(n-xd,d)f(x)\\ =\sum_{x=1}^n f(x)\sum_{d=1}^{\lfloor\frac{n-1}{x}\rfloor}\mathrm{lcm}(n-xd,d) \]注意到对于每个 \(x\)，\(d\) 只会枚举到 \(\lfloor\frac{n-1}{x} \rfloor\)，所以该式可以 \(O(n\log n)\) 求出。
最终时间复杂度 \(O(n\sqrt n + n\log n)\)。
Code
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL MOD = 1e9 + 7;
const int maxn = 100005;
int mu[maxn];
bool not_prime[maxn];
vector<int> prime;
void get_mu(int len) {
mu[1] = not_prime[1] = 1;
for (int i = 2;i <= len;++i) {
if (!not_prime[i]) { prime.push_back(i); mu[i] = -1; }
for (auto j : prime) {
int mid = i * j;
if (mid > len) break;
not_prime[mid] = 1;
if (i % j == 0) { mu[mid] = 0; break; }
mu[mid] = -mu[i];
}
}
}
int f[maxn], g[maxn];
int main() {
get_mu(100000);
int n;cin >> n;
for (int x = 1;x <= n;++x) {
int c = 1;
for (c = 1;c * c < x;++c) {
if (x % c == 0) {
f[x] += mu[c] * (x / c - 1);
f[x] += mu[x / c] * (c - 1);
}
}
if (c * c == x) f[x] += mu[c] * (x / c - 1);
}
LL ans = 0;
for (int x = 1;x < n;++x) {
LL temp = 0;
for (int d = 1;d <= (n - 1) / x;++d)
temp = (temp + ((n - x * d) / __gcd(n - x * d, d) * d)) % MOD;
ans = (ans + temp * f[x] % MOD) % MOD;
}
cout << ans << endl;
return 0;
}