题目链接

2702. problem b
同215. 破译密码

对于给出的 \(n\) 个询问，每次求有多少个数对 \((x,y)\)，满足 \(a≤x≤b，c≤y≤d\)，且 \(\text{gcd}(x,y) = k\)，\(\text{gcd}(x,y)\) 函数为 \(x\) 和 \(y\) 的最大公约数。

输入格式

第一行一个整数 \(n\)。

接下来 \(n\) 行每行五个整数，分别表示 \(a、b、c、d、k\)。

输出格式

共 \(n\) 行，每行一个整数表示满足要求的数对 \((x,y)\) 的个数。

数据范围

\(1 \le n \le 50000\),
\(1 \le a \le b \le 50000\),
\(1 \le c \le d \le 50000\),
\(1 \le k \le 50000\)

输入样例：

2
2 5 1 5 1
1 5 1 5 2

输出样例：

14
3

解题思路

莫比乌斯反演

本题单用容斥原理和莫比乌斯函数也可做：215. 破译密码

这里介绍莫比乌斯反演做法

先给出莫比乌斯函数的一个性质：\(\sum_{d \mid n} \mu(d)= \begin{cases}1 & n=1 \\ 0 & n \neq 1\end{cases}\) 。简略证明：\(n=1\) 时显然。当 \(n>1\) 时，对 \(n\) 分解质因数：\(n=\prod_{i=1}^{k} p_{i}^{c_{i}}\)，当存在 \(c_i>1\) 时该项表示的约数的 \(d\) 的 \(\mu(d)=0\)，这种情况的约数不考虑，即只用考虑 \(\prod_{i=1}^{k} p_{i}\) 的约数，即在这 \(k\) 个数中选出 \(1\) 个数组成约数，\(2\) 组成约数，\(3\) 个数组成约数，\(\dots\)，组成 \(k\) 个数组成约数，由莫比乌斯函数，奇数种质数为 \(-1\)，偶数种质数为 \(1\)，则 \(\sum_{d \mid n} \mu(d)=\sum_{i=0}^{k} C_{k}^{i} \cdot(-1)^{i}=(1+(-1))^{k}=0\)
接着，有莫比乌斯反演的两条重要定理：

1. 如果有 \(F(n)=\sum_{d \mid n} f(d)\) ，那么有 \(f(n)=\sum_{d \mid n} \mu(d) F\left(\frac{n}{d}\right)\)
   证明：将 \(F(n)=\sum_{d \mid n} f(d)\) 代入，得 \(\sum_{d \mid n} \mu(d) \sum_{i\mid \frac{n}{d}}f[i]\)，观察 \(i\) 和 \(d\) 配对的情况，当 \(d=1\) 时 \(i\) 取遍 \(n\) 的约数，而对于某个固定的 \(i\)，要求找出与 \(i\) 配对的 \(d\)，这样的 \(d\) 需满足：\(d\mid n,i\mid \frac{n}{d}\)，即 \(d\mid \frac{n}{i}\)，此时可以交换 \(i,d\) 顺序，即：\(\sum_{i \mid n} f(i) \sum_{d\mid \frac{n}{i}}\mu(d)\)，由莫比乌斯函数约数和性质，当且仅当 \(i=n\) 时后面的和不为 \(0\)，即\(\sum_{i \mid n} f(i) \sum_{d\mid \frac{n}{i}}\mu(d)=f(n)\)

2. 如果有 \(F(n)=\sum_{n \mid d} f(d)\) ，那么有 \(f(n)=\sum_{n \mid d} \mu\left(\frac{d}{n}\right) F(d)\)
   同理。这条定理常用。

本题按前缀和可转化为求解：\(\sum_{i=1}^{a} \sum_{j=1}^{b}[(i, j)=n]\)，其中 \((i,j)\) 表示 \(i\) 和 \(j\) 的最大公约数

由莫比乌斯反演的性质，求解 \(F(n)\) 容易，求解 \(f(n)\) 困难，本题中 \(f(n)=\sum_{i=1}^{a} \sum_{j=1}^{b}[(i, j)=n]\)，而由莫比乌斯反演第二条定理，可设定 \(F(n)=\sum_{i=1}^{a} \sum_{j=1}^{b}[n\mid (i, j)]\)，其含义表示的是 \(x\in [1,a],y\in [1,b]\) 中 \(gcd(x,y)\) 是 \(n\) 的倍数的点数，\([1,a]\) 中有 \(a/n\) 个值是 \(n\) 的倍数，\([1,b]\) 中有 \(b/n\) 个值是 \(n\) 的倍数，由乘法原理，共有 \((a/n)\times (b/n)\) 个点满足要求，即 \(F(n)=(a/n)\times (b/n)\)，则 $f(n)=\sum_{n \mid d} \mu\left(\frac{d}{n}\right)(a/d)\times (b/d) $，令 \(d'=\frac{d}{n}\)，则 $f(n)=\sum_{d'} \mu(d')(a/d'n)\times (b/d'n) $，而倍数 \(d'\) 也不能无限大，$(d')(a/d'n)\times (b/d'n) $ 导致 \(d'\) 最大为 \(n=min(a/n,b/n)\)，令 \(a=a/n,b=b/n\)，即 $f(n)=\sum_{i=1}^n\mu(i)(a/i)\times (b/i) $，此时转化为单靠容斥原理得到的结论

• 时间复杂度：\((n\sqrt{n})\)

代码

// Problem: problem b
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2704/
// Memory Limit: 64 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=5e4+5;
int q,a,b,c,d,k,m,prime[N],v[N],u[N],s[N];
void primes(int n)
{
    u[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(v[i]==0)
        {
            u[i]=-1;
            v[i]=prime[++m]=i;
        }
        for(int j=1;prime[j]*i<=n&&j<=m;j++)
        {
            if(v[i]<prime[j])break;
            if(i%prime[j]==0)
                u[i*prime[j]]=0;
            else
                u[i*prime[j]]=-u[i];
            v[i*prime[j]]=prime[j];

        }
    }
    for(int i=1;i<=n;i++)s[i]=s[i-1]+u[i];
}
int g(int a,int b)
{
	return a/(a/b);
}
LL f(int a,int b,int d)
{
	LL res=0;
	a/=d,b/=d;
	int n=min(a,b);
	for(int l=1,r;l<=n;l=r+1)
	{
		r=min({n,g(a,l),g(b,l)});
		res+=1ll*(s[r]-s[l-1])*(a/l)*(b/l);
	}
	return res;
}
int main()
{
    primes(N-1);
    cin>>q;
    while(q--)
    {
    	cin>>a>>b>>c>>d>>k;
    	cout<<f(b,d,k)-f(b,c-1,k)-f(a-1,d,k)+f(a-1,c-1,k)<<'\n';
    }
    return 0;
}