题目链接

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;
}