冬令营考炸了，我这个菜鸡只好颓废数学题了
NOI2010能量采集
由题意可以写出式子：
\(\sum_{i=1}^n\sum_{j=1}^m(2\gcd(i,j)-1)\)
\(=2\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)-nm\)
我们现在考虑\(\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)\)，默认n比m小
\(=\sum_{p=1}^np\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=p]\)
\(=\sum_{p=1}^np\sum_{i=1}^{n/p}\sum_{j=1}^{m/p}[gcd(i,j)=1]\)
\(=\sum_{p=1}^np\sum_{i=1}^{n/p}\sum_{j=1}^{m/p}\sum_{d|i,d|j}\mu(d)\)
\(=\sum_{p=1}^np\sum_{d=1}^n\mu(d)\lfloor\frac n{pd}\rfloor\lfloor\frac m{pd}\rfloor\)
\(=\sum_{q=1}^n\sum_{d|q}\mu(d)\frac qd\lfloor\frac n{q}\rfloor\lfloor\frac m{q}\rfloor\)
由于是单组数据，所以不用前缀和数论分块
所以这是一道莫比乌斯反演题，32行一遍AC
#include <cstdio>
using namespace std;
bool vis[100010];
int mu[100010], tot, prime[100010], fuck = 100000;
long long sum[100010];
int main()
{
mu[1] = 1;
for (int i = 2; i <= fuck; i++)
{
if (vis[i] == 0) prime[++tot] = i, mu[i] = -1;
for (int j = 1; j <= tot && i * prime[j] <= fuck; j++)
{
vis[i * prime[j]] = true;
if (i % prime[j] == 0) break;
mu[i * prime[j]] = -mu[i];
}
}
for (int i = 1; i <= fuck; i++)
for (int j = i, k = 1; j <= fuck; j += i, k++)
sum[j] += mu[i] * k;
int n, m;
scanf("%d%d", &n, &m);
if (n > m) { int t = n; n = m; m = t; }
long long ans = 0;
for (int i = 1; i <= n; i++)
ans += sum[i] * (n / i) * (m / i);
printf("%lld\n", ans * 2 - n * (long long)m);
return 0;
}