求值（多组数据）
$math_inline$ \sum_{i=x}^{n}\sum_{j=y}^{m}[\gcd(i,j)=k]\qquad (1\leqslant T,x,y,n,m,k\leqslant 5\times 10^4) $math_inline$根据容斥原理，原式可以分成 $math_inline$4$math_inline$ 块来处理，每一块的式子都为
$math_inline$ \sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=k] $math_inline$考虑化简该式子
$math_inline$ \sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[\gcd(i,j)=1] $math_inline$因为 $math_inline$\gcd(i,j)=1$math_inline$ 时对答案才用贡献，于是我们可以将其替换为 $math_inline$\varepsilon(\gcd(i,j))$math_inline$ （ $math_inline$\varepsilon(n)$math_inline$ 当且仅当 $math_inline$n=1$math_inline$ 时值为 $math_inline$1$math_inline$ 否则为 $math_inline$0$math_inline$ ），故原式化为
$math_inline$ \sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}\varepsilon(\gcd(i,j)) $math_inline$将 $math_inline$\varepsilon$math_inline$ 函数展开得到
$math_inline$ \displaystyle\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}\sum_{d\mid \gcd(i,j)}\mu(d) $math_inline$变换求和顺序，先枚举 $math_inline$d\mid gcd(i,j)$math_inline$ 可得
$math_inline$ \displaystyle\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}d\mid i\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}d\mid j $math_inline$（其中 $math_inline$d\mid i$math_inline$ 表示 $math_inline$i$math_inline$ 是 $math_inline$d$math_inline$ 的倍数时对答案有 $math_inline$1$math_inline$ 的贡献） 易知 $math_inline$1\sim\lfloor\dfrac{n}{k}\rfloor$math_inline$ 中 $math_inline$d$math_inline$ 的倍数有 $math_inline$\lfloor\dfrac{n}{kd}\rfloor$math_inline$ 个，故原式化为
$math_inline$ \displaystyle\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d) \lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor $math_inline$很显然，式子可以数论分块求解（注意：过程中默认 $math_inline$n\leqslant m$math_inline$ ）。
时间复杂度 ： $math_inline$\Theta(N+T\sqrt{n})$math_inline$
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 50000;
int mu[N + 5], p[N + 5];
bool flg[N + 5];
void init() {
int tot = 0;
mu[1] = 1;
for (int i = 2; i <= N; ++i) {
if (!flg[i]) {
p[++tot] = i;
mu[i] = -1;
}
for (int j = 1; j <= tot && i * p[j] <= N; ++j) {
flg[i * p[j]] = 1;
if (i % p[j] == 0) {
mu[i * p[j]] = 0;
break;
}
mu[i * p[j]] = -mu[i];
}
}
for (int i = 1; i <= N; ++i) mu[i] += mu[i - 1];
}
int solve(int n, int m) {
int res = 0;
for (int i = 1, j; i <= std::min(n, m); i = j + 1) {
j = std::min(n / (n / i), m / (m / i));
res += (mu[j] - mu[i - 1]) * (n / i) * (m / i);
}
return res;
}
int main() {
int T, a, b, c, d, k;
init();
cin >> T;
while (T--) {
cin >> a >> b >> c >> d >> k;
cout << solve(b / k, d / k)
- solve(b / k, (c - 1) / k)
- solve((a - 1) / k, d / k)
+ solve((a - 1) / k, (c - 1) / k) << endl;
}
return 0;
}
Code 2
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
namespace SOL {
const int MAXN = 50011;
const int MAXL = 50000;
LL a, b, c, d, k, ans;
int prime[MAXN], cnt;
bool ok[MAXN];
int mobius[MAXN], sum[MAXN]; //莫比乌斯函数及其前缀和
inline void init() { //递推得到莫比乌斯函数
//1的莫比乌斯函数是1；质数的莫比乌斯函数为1；含有相同质因子的数莫比乌斯函数为0；
//不含有相同质因子的数的莫比乌斯函数函数为（-1）^k，k为质因子个数
mobius[1] = 1;
for (int i = 2; i <= MAXL; i++) {
if (!ok[i]) {
mobius[i] = -1;
prime[++cnt] = i;
}
for (int j = 1; j <= cnt && i * prime[j] <= MAXL; j++) {
ok[i * prime[j]] = 1;//标记合数
if (i % prime[j]) mobius[i * prime[j]] = -mobius[i];//互质的两个数乘起来得到一个不含有相同质因子的数，质因子个数奇偶性改变，莫比乌斯函数变号
else {
mobius[i * prime[j]] = 0;
break;
}//留到后面再筛，此处已经可以break
}
}
for (int i = 1; i <= MAXL; i++) sum[i] = sum[i - 1] + mobius[i];//求莫比乌斯函数的前缀和
}
inline LL solve(LL n, LL m) {//计算a在[1,n]且b在[1,m]中的gcd(a,b)==1的数目
n /= k;
m /= k;
if (n > m) swap(n, m);
if (n == 0) return 0;
LL i, next1, next2, next;//把相等的部分直接分块一起计算
LL tot = 0;
for (i = 1; i <= n; i = next) {
next1 = n / (n / i);
next2 = m / (m / i);
next = min(next1, next2);
tot += (n / i) * (m / i) * (sum[next] - sum[i - 1]);
next++;
}
return tot;
}
inline void work() {
int T;
cin >> T;
init();
while (T--) {
cin >> a >> b >> c >> d >> k;
ans = solve(b, d) - solve(a - 1, d) - solve(b, c - 1) + solve(a - 1, c - 1);//容斥原理
cout << ans << endl;
}
}
}
int main() {
SOL::work();
return 0;
}