BZOJ 2005
题意：
给定$n,m$，求
$$
2 \times \sum_{i=1}^n\sum_{j=1}^m (\gcd(i,j) -1)
$$
按照套路反演以后得到
$$
\sum_{d=1}^n d \sum_{i=1}^{\lfloor \frac nd \rfloor} \mu(i) \lfloor \frac n{di} \rfloor \lfloor \frac m{di}\rfloor
$$
然后我们设$T=di$，则
$$
\sum_{T=1}^n \lfloor \frac nT \rfloor \lfloor \frac mT \rfloor \sum_{d|T} \mu(d) \lfloor \frac Tk \rfloor
$$
设$h(T)=\sum_{d|T} \mu(d) \lfloor \frac Tk \rfloor$，则可以线性筛。
也可以发现这就是欧拉函数，直接筛欧拉函数即可。
答案为
$$
2 \times \sum_{i=1}^n\sum_{j=1}^m \gcd(i,j) - nm
$$
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const LL MAXN = 100000 + 5;
LL n, m;
LL pri[MAXN], vis[MAXN], tot, h[MAXN];
void clean() {
ms(vis, 0), tot = 0;
}
int solve() {
clean();
scanf("%lld%lld", &n, &m);
if (n > m) swap(n, m);
h[1] = 1;
for (LL i = 2; i <= m; ++i) {
if (!vis[i]) pri[++tot] = i, h[i] = i - 1;
for (LL j = 1; j <= tot && i * pri[j] <= m; ++j) {
vis[pri[j] * i] = 1;
if (i % pri[j] == 0) {
h[i * pri[j]] = h[i] * pri[j];
break ;
} else h[i * pri[j]] = h[i] * h[pri[j]];
}
}
for (LL i = 1; i <= m; ++i) h[i] += h[i - 1];
LL ans = 0, l = 1;
while (l <= n) {
LL r = min(n / (n / l), m / (m / l));
ans += (n / l) * (m / l) * (h[r] - h[l - 1]);
l = r + 1;
}
printf("%lld\n", 2 * ans - n * m);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
