BZOJ 2301
题意：给定$a, b, c, d, k$, 求
$$
\sum_{i=a}^{b} \sum_{j=c}^{d} [\gcd(i,j)=k]
$$
(下面默认$n \leq m$, 不满足则交换)
解：
我们可以将答案分成几个部分求解，然后$ans=f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,c-1)$
依题意设出$f(k)$为$gcd(i,j)=k$的个数$(1 \leq i \leq n, 1 \leq j \leq n)$
但是这个并不好求，看见两个求和符号，我们可以想到用莫比乌斯反演来求解。
显然用变形后的两个式子，我们就可以设$g(k)$为$k|gcd(i,j)$的个数$(1 \leq i \leq n, 1 \leq j \leq n)$
$g(k)$非常好算，$g(k)=\lfloor \frac n{k} \rfloor \lfloor \frac m{k} \rfloor$
而显然$g(k)=\sum_{d=1}^{\lfloor \frac nk \rfloor} f(ki)$
那么可以莫比乌斯反演
$$
f(k)=\sum_{d=1}^{\lfloor \frac nk \rfloor} \mu(d) \lfloor \frac n{kd} \rfloor \lfloor \frac m{kd} \rfloor
$$
换元$\lfloor \frac nk \rfloor$，整除分块即可。
注意有$n,m$的整除分块是取两者最小值，复杂度也是有保证的。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const LL MAXN = 50000 + 5;
LL q, tot, pri[MAXN], vis[MAXN], mu[MAXN];
LL getans(LL n, LL m, LL k) {
if (n > m) swap(n, m);
n /= k, m /= k;
LL l = 1, r, ans = 0ll;
while (l <= n) {
r = min((n / (n / l)), (m / (m / l)));
ans += (n / l) * (m / l) * (mu[r] - mu[l - 1]);
l = r + 1ll;
}
return ans;
}
void clean() {
ms(vis, 0), tot = 0;
}
int solve() {
scanf("%lld", &q);
clean();
vis[1] = 1, mu[1] = 1;
for (LL i = 2; i <= 50000; ++i) {
if (!vis[i]) mu[i] = -1, pri[++tot] = i;
for (LL j = 1; j <= tot && i * pri[j] <= 50000; ++j) {
vis[i * pri[j]] = 1;
if (i % pri[j] == 0) {
mu[i * pri[j]] = 0;
break;
} else mu[i * pri[j]] = -mu[i];
}
}
//for (LL i = 1; i <= 100; ++i) cerr << mu[i] << " ";
mu[0] = 0;
for (LL i = 1; i <= 50000; ++i) mu[i] += mu[i - 1];
for (LL a, b, c, d, k, i = 1; i <= q; ++i) {
scanf("%lld%lld%lld%lld%lld", &a, &b, &c, &d, &k);
printf("%lld\n", getans(b, d, k) - getans(a - 1, d, k) - getans(b, c - 1, k) + getans(a - 1, c - 1, k));
}
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
