problem_b问题

解题思路：

本题要求 $x$ 在 $[a,b]$ 区间内，$y$ 在 $[c,d]$ 区间内，有多少对 $x,y$ 满足 $gcd(x,y)=k$。

等价于是问在二维坐标系中，有一个矩形，左下角为 $(a,c)$，右上角是 $(b,d)$，问有多少个在矩形中的点 $(x,y)$ 满足 $gcd(x,y)=k$。这里用二维前缀和的思想，设 $S_{x,y}$ 表示左下角为 $(0,0)$，右上角为 $(x,y)$ 的矩形中有多少个点 $(u,v)$ 满足 $gcd(u,v)=k$。那么原题目问的其实就是 $S_{b,d}-S_{a-1,d}-S_{b,c-1}+S_{a-1,c-1}$。

那么接下来的问题就是我们要求出任意的 $S_{a,b}$（区别于上面的 $a,b$），这样就能通过二维前缀和的技巧求出任意一个矩形中的点对数量了。

这题是可以用容斥原理求出来的，这里用莫比乌斯反演来求。要想用莫比乌斯反演来求，我们就需要定义出 $F(n)$ 和 $f(n)$，使得 $F(n)=\sum_{n\vert d} f(d)$，并且 $F(n)$ 要比较好求，这样根据莫比乌斯反演的推论 $f(n)=\sum_{n\vert d} \mu{(\frac{d}{n})} F(d)$，我们就能用 $F(n)$ 求出 $f(n)$。

这里设 $F(n)=\sum_{x=1}^a\sum_{y=1}^b[n \vert gcd(x,y)]$，对于任意的 $(x,y)$，如果 $gcd(x,y)$ 能整除 $n$ 则返回 $1$，不能则返回 $0$，则 $F(n)$ 的实际意义就是在 $(0,0)$ 到 $(a,b)$ 的矩形中 $(x,y)$ 的最大公约数是 $n$ 的倍数的点的数量。

设 $f(n)=\sum_{x=1}^a\sum_{y=1}^b[gcd(x,y)=n]$，同理，对于任意的 $(x,y)$，如果 $gcd(x,y)=n$ 返回 $1$，$gcd(x,y) \neq n$ 返回 $0$，则 $f(n)$ 的实际意义就是在 $(0,0)$ 到 $(a,b)$ 的矩形中 $(x,y)$ 的最大公约数恰好是 $n$ 的点的数量。则我们要求的就是 $f(k)$

可以发现 $F(n)$ 求的是所有 $gcd(x,y)$ 是 $n$ 的倍数的点数，而 $f(n)$ 求的是 $gcd(x,y)$ 是 $n$ 的点数，因此 $F(n)$ 恰好就是 $\sum_{n \vert d} f(d)$。这就满足了莫比乌斯反演推论的条件，我们就能用 $F(n)$ 来求 $f(n)$ 了，$f(n)=\sum_{n\vert d} \mu{(\frac{d}{n})} F(d)$。

那么要想用公式求出 $f(n)$，我们就需要求出 $F(d)$，也就是最大公约数是 $d$ 的倍数的点的数量，如果 $x$ 和 $y$ 的最大公约数能整除 $d$，这就意味着 $x$ 和 $y$ 也能整除 $d$。因此 $F(d)$ 就是要统计一下有多少个点的横、纵坐标都是 $d$ 的倍数。其实就是看一下有多少个横坐标是 $d$ 的倍数，有多少个纵坐标是 $d$ 的倍数，组合一下就是总的点数，也就是 $\lfloor \frac{a}{d} \rfloor \lfloor \frac{b}{d} \rfloor$。

那么我们现在的目标就是求 $f(n)=\sum_{n\vert d} \mu{(\frac{d}{n})} \lfloor \frac{a}{d} \rfloor \lfloor \frac{b}{d} \rfloor$，我们设 $d’ = \frac{d}{n}$，则式子变成 $\sum_{d’} \mu{(d’)} \lfloor \frac{a}{d’n} \rfloor \lfloor \frac{b}{d’n} \rfloor$，并且此时 $d’$ 的取值变成从 $1$ 开始以 $1$ 递增的序列，更容易处理。然后可以发现 $a,b,n$ 是三个固定的数，并且和 $d’$ 没有任何关联，因此我们再设 $a’=\frac{a}{n},b’=\frac{b}{n}$，则式子进一步变成 $\sum_{d’} \mu{(d’)} \lfloor \frac{a’}{d’} \rfloor \lfloor \frac{b’}{d’} \rfloor$

然后可以发现我们式子中需要频繁计算 $\lfloor \frac{k}{x} \rfloor$，它一共只会有 $2\sqrt{k}$ 种取值，这是一个整数分块的知识点。也比较容易理解，首先 $\frac{k}{x}$ 随着 $x$ 的增加是单调递减的，当 $x=1\sim \sqrt{k}$ 时有 $\sqrt{k}$ 个取值，当 $x=\sqrt{k}+1\sim k$，则 $1 \leq \frac{k}{x} < \sqrt{k}$，因此两段取值分别都只有 $\sqrt{k}$ 种取值，因此总共只会有 $2\sqrt{k}$ 个取值。并且每一种取值都是一段连续的区间，如果设 $g(x)$ 为和 $x$ 取值相同的区间中的最后一个数，而 $g(x)= \lfloor \frac{k}{\lfloor \frac{k}{x} \rfloor} \rfloor$，在每个区间内 $\frac{k}{x}$ 的取值都是相同的，因此我们就可以直接对于每个区间计算值。

而我们的式子中有两个 $\frac{k}{x}$，因此我们需要将两个都考虑进去，由于超过 $a’$ 或 $b’$ 值就为 $0$ 了，因此我们只需要考虑 $1 \sim min(a’,b’)$，对于 $\frac{a’}{d’}$，会将区间分成 $O(\sqrt{n})$ 段，对于 $\frac{b’}{d’}$，也会将区间分成 $O(\sqrt{n})$ 段，算上两个式子，此时整个区间仍然还是 $O(\sqrt{n})$ 段，而在每一段区间中，$\frac{a’}{d’}$ 和 $\frac{b’}{d’}$ 的取值都是相同的，这样我们只需要一段一段的统一考虑即可，每一段中，我们只需要知道这个区间中 $\sim_{d’} \mu{(d’)}$ 的值是多少就行了，由于我们知道每个区间的左、右端点，因此我们只需要预处理莫比乌斯函数的前缀和，然后用区间和的思想求出每个区间中的莫比乌斯函数的值的和。这样我们就能将整个式子的结果求出来。并且由于只有 $O(\sqrt{n})$ 段区间，因此整个的时间复杂度也是 $O(\sqrt{n})$

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 50010;

int primes[N], cnt; //存储所有质数
bool st[N]; //记录每个数是不是合数
int mu[N]; //莫比乌斯函数
int sum[N]; //莫比乌斯函数的前缀和

void init(int n) //预处理莫比乌斯函数
{
    //线性筛法求莫比乌斯函数
    mu[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) primes[cnt++] = i, mu[i] = -1;
        for(int j = 0; primes[j] <= n / i; j++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
            mu[primes[j] * i] = -mu[i];
        }
    }
    for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + mu[i]; //预处理前缀和
}

int g(int k, int x) //返回 x 所在区间的最后一个数
{
    return k / (k / x);
}

LL f(int a, int b, int k) //求 f(k)，f(k) 表示在 (0,0) ~ (a,b) 的矩阵中满足 gcd(x,y) == k 的点的数量
{
    a /= k, b /= k;
    LL res = 0; //记录答案
    int n = min(a, b);
    for(int l = 1, r; l <= n; l = r + 1) //枚举区间左端点
    {
        r = min(n, min(g(a, l), g(b, l))); //计算右端点
        res += (LL)(sum[r] - sum[l - 1]) * (a / l) * (b / l); //累加答案
    }
    return res; //返回答案
}

int main()
{
    init(N - 1); //预处理

    int T;
    scanf("%d", &T);
    while(T--)
    {
        int a, b, c, d, k;
        scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
        printf("%lld\n", f(b, d, k) - f(a - 1, d, k) - f(b, c - 1, k) + f(a - 1, c - 1, k));
    }
    return 0;
}