传送门 ↬\looparrowright

题目描述

对于给出的 nn 个询问，每次求有多少个数对 (x,y)(x,y)，满足 a≤x≤ba \le x \le b，c≤y≤dc \le y \le d，且gcd⁡(x,y)=k\gcd(x,y) = k，gcd⁡(x,y)\gcd(x,y) 函数为 xx 和 yy 的最大公约数。

输入格式

第一行一个整数 nn，接下来 nn 行每行五个整数，分别表示 a,b,c,d,ka,b,c,d,k。

输出格式

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

输入输出样例

输入 #1

2
2 5 1 5 1
1 5 1 5 2

输出 #1

14
3

说明/提示

对于 100%100\% 的数据满足：1≤n,k≤5×1041 \le n,k \le 5 \times 10^4，1≤a≤b≤5×1041 \le a \le b \le 5 \times 10^4，1≤c≤d≤5×1041 \le c \le d \le 5 \times 10^4。

分析

令二元函数 f(x,y)=∑i=1x∑j=1y[gcd⁡(i,j)=k]f(x,y)=\sum\limits_{i=1}^x\sum\limits_{j=1}^y [\gcd(i,j)=k]，其中 $x,y\in \mathbb N^\ast$。由题意，所求答案为 $\sum\limits_{i=a}^b\sum\limits_{j=c}^d[\gcd(i,j)=k]$；依据容斥原理，ans=f(b,d)−f(a−1,d)−f(b,c−1)+f(a−1,c−1)ans=f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,c-1)。
任务转化为，对于给定的 $n,m\in \mathbb N^\ast$，求 $f(n,m)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m [\gcd(i,j)=k]$ 的值。
首先，kk 为 i,ji,j 的最大公约数，故 ik\frac{i}{k} 与 jk\frac{j}{k} 互质，即 gcd⁡(ik,jk)=1\gcd(\frac{i}{k},\frac{j}{k})=1。所以 $f(n,m)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m \left[\gcd\left(\frac{i}{k},\frac{j}{k}\right)=1\right]$；从此式看出，ik\frac{i}{k} 的上限为 ⌊nk⌋\left\lfloor\frac{n}{k}\right\rfloor，jk\frac{j}{k} 的上限为 ⌊mk⌋\left\lfloor\frac{m}{k}\right\rfloor；因此等价于， f(n,m)=\sum\limits_{i=1}^\left\lfloor\frac{n}{k}\right\rfloor\sum\limits_{j=1}^\left\lfloor\frac{m}{k}\right\rfloor[\gcd(i,j)=1]。
接下来利用莫比乌斯反演的性质，gcd⁡(i,j)=1⇔∑d∣gcd⁡(i,j)μ(d)\gcd(i,j)=1\Leftrightarrow\sum\limits_{d\mid\gcd(i,j)}\mu(d)。故 f(n,m)=\sum\limits_{i=1}^\left\lfloor\frac{n}{k}\right\rfloor\sum\limits_{j=1}^\left\lfloor\frac{m}{k}\right\rfloor\sum\limits_{d\mid\gcd(i,j)}\mu(d)。
接下来变换求和次序，改为枚举 dd。f(n,m)=\sum\limits_{d=1}^{\min\left(\left\lfloor\frac{n}{k}\right\rfloor,\left\lfloor\frac{n}{k}\right\rfloor\right)}\sum\limits_{i=1}^\left\lfloor\frac{n}{k}\right\rfloor\sum\limits_{j=1}^\left\lfloor\frac{m}{k}\right\rfloor\mu(d)[d\mid\gcd(i,j)]；由于 μ(d)\mu(d) 为只与 dd 相关的函数，则 f(n,m)=\sum\limits_{d=1}^{\min\left(\left\lfloor\frac{n}{k}\right\rfloor,\left\lfloor\frac{n}{k}\right\rfloor\right)}\mu(d)\sum\limits_{i=1}^\left\lfloor\frac{n}{k}\right\rfloor\sum\limits_{j=1}^\left\lfloor\frac{m}{k}\right\rfloor[d\mid\gcd(i,j)]。
有条件 d∣gcd⁡(i,j)d\mid\gcd(i,j)，故可设 gcd⁡(i,j)=pd\gcd(i,j)=pd；由最大公约数的定义 pd∣ipd\mid i 且 pd∣jpd\mid j，因此假设 i=p1pdi=p_1pd，j=p2pdj=p_2pd；其中，p,p1,p2∈N∗p,p_1,p_2\in \mathbb N^\ast。经过上述略证， d∣gcd⁡(i,j)d\mid\gcd(i,j) 的充要条件是：i,ji,j 都为 dd 的倍数。在区间 [1,⌊nk⌋]\left[1,\left\lfloor\frac{n}{k}\right\rfloor\right] 中，dd 的倍数有 ⌊⌊nk⌋d⌋\left\lfloor\frac{\left\lfloor\frac{n}{k}\right\rfloor}{d}\right\rfloor 个；在区间 [1,⌊mk⌋]\left[1,\left\lfloor\frac{m}{k}\right\rfloor\right] 中，dd 的倍数有 ⌊⌊mk⌋d⌋\left\lfloor\frac{\left\lfloor\frac{m}{k}\right\rfloor}{d}\right\rfloor 个；因此，满足条件 d∣gcd⁡(i,j)d\mid\gcd(i,j) 的数对 (i,j)(i,j) 的个数有 \sum\limits_{i=1}^\left\lfloor\frac{n}{k}\right\rfloor\sum\limits_{j=1}^\left\lfloor\frac{m}{k}\right\rfloor[d\mid\gcd(i,j)]=\left\lfloor\frac{\left\lfloor\frac{n}{k}\right\rfloor}{d}\right\rfloor\times\left\lfloor\frac{\left\lfloor\frac{m}{k}\right\rfloor}{d}\right\rfloor。
将 \sum\limits_{i=1}^\left\lfloor\frac{n}{k}\right\rfloor\sum\limits_{j=1}^\left\lfloor\frac{m}{k}\right\rfloor[d\mid\gcd(i,j)]=\left\lfloor\frac{\left\lfloor\frac{n}{k}\right\rfloor}{d}\right\rfloor\times\left\lfloor\frac{\left\lfloor\frac{m}{k}\right\rfloor}{d}\right\rfloor 代入，得 f(n,m)=∑d=1min⁡(⌊nk⌋,⌊nk⌋)⌊⌊nk⌋d⌋⌊⌊mk⌋d⌋μ(d)f(n,m)=\sum\limits_{d=1}^{\min\left(\left\lfloor\frac{n}{k}\right\rfloor,\left\lfloor\frac{n}{k}\right\rfloor\right)}\left\lfloor\frac{\left\lfloor\frac{n}{k}\right\rfloor}{d}\right\rfloor\left\lfloor\frac{\left\lfloor\frac{m}{k}\right\rfloor}{d}\right\rfloor\mu(d)。该式可用数论分块解决。
结合以上

$\begin{aligned}f(n,m)&=\sum\limits_{i=1}^n\sum\limits_{j=1}^m [\gcd(i,j)=k]\\&=\sum\limits_{i=1}^n\sum\limits_{j=1}^m \left[\gcd\left(\frac{i}{k},\frac{j}{k}\right)=1\right]\\&=\sum\limits_{i=1}^\left\lfloor\frac{n}{k}\right\rfloor\sum\limits_{j=1}^\left\lfloor\frac{m}{k}\right\rfloor[\gcd(i,j)=1]\\&=\sum\limits_{i=1}^\left\lfloor\frac{n}{k}\right\rfloor\sum\limits_{j=1}^\left\lfloor\frac{m}{k}\right\rfloor\sum\limits_{d\mid\gcd(i,j)}\mu(d)\\&=\sum\limits_{d=1}^{\min\left(\left\lfloor\frac{n}{k}\right\rfloor,\left\lfloor\frac{n}{k}\right\rfloor\right)}\sum\limits_{i=1}^\left\lfloor\frac{n}{k}\right\rfloor\sum\limits_{j=1}^\left\lfloor\frac{m}{k}\right\rfloor\mu(d)[d\mid\gcd(i,j)]\\&=\sum\limits_{d=1}^{\min\left(\left\lfloor\frac{n}{k}\right\rfloor,\left\lfloor\frac{n}{k}\right\rfloor\right)}\mu(d)\sum\limits_{i=1}^\left\lfloor\frac{n}{k}\right\rfloor\sum\limits_{j=1}^\left\lfloor\frac{m}{k}\right\rfloor[d\mid\gcd(i,j)]\\&=\sum\limits_{d=1}^{\min\left(\left\lfloor\frac{n}{k}\right\rfloor,\left\lfloor\frac{n}{k}\right\rfloor\right)}\left\lfloor\frac{\left\lfloor\frac{n}{k}\right\rfloor}{d}\right\rfloor\left\lfloor\frac{\left\lfloor\frac{m}{k}\right\rfloor}{d}\right\rfloor\mu(d)\end{aligned}$

综上所述，对于给定的 n,mn,m 最终用数论分块求解 f(n,m)f(n,m) 的值 。假设在区间 [l,r][l,r] 内，⌊⌊nk⌋d⌋×⌊⌊mk⌋d⌋\left\lfloor\frac{\left\lfloor\frac{n}{k}\right\rfloor}{d}\right\rfloor\times\left\lfloor\frac{\left\lfloor\frac{m}{k}\right\rfloor}{d}\right\rfloor 恒为 AA，则 ∑d=lr⌊⌊nk⌋d⌋⌊⌊mk⌋d⌋μ(d)=A∑d=lrμ(d)\sum\limits_{d=l}^r\left\lfloor\frac{\left\lfloor\frac{n}{k}\right\rfloor}{d}\right\rfloor\left\lfloor\frac{\left\lfloor\frac{m}{k}\right\rfloor}{d}\right\rfloor\mu(d)=A\sum\limits_{d=l}^r\mu(d)；显然，我们要预处理莫比乌斯函数的前缀和，才能在 O(1)O(1) 内求出和式一个分块的值。
题目的最终答案为 f(b,d)−f(a−1,d)−f(b,c−1)+f(a−1,c−1)f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,c-1)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
#define N 50006
using namespace std;
bool vis[N];
int prime[N>>1];//质数
int mu[N];//莫比乌斯函数
int sum[N];//mu[i]的前缀和
int cnt;
int a,b,c,d,k;
//--------------------------------------------
//欧拉筛求得莫比乌斯函数
//求莫比乌斯函数的前缀和
void init(int n)
{
	mu[1]=1;
	int i,j;
	for(i=2;i<=n;i++)
	{
		if(!vis[i])
		{
			prime[++cnt]=i;
			mu[i]=-1;
		}
		for(j=1;j<=cnt&&i*prime[j]<=n;j++)
		{
			vis[i*prime[j]]=1;
			if(i%prime[j]==0) 
			{
				mu[i*prime[j]]=0;
				break;
			}
			else mu[i*prime[j]]=-mu[i];
		}
	}
	for(i=1;i<=n;i++) sum[i]=sum[i-1]+mu[i];
}
//--------------------------------------------
//--------------------------------------------------
//对于给定的n,m
//计算f(n,m)
//将n/k,m/k看作整体
inline ll f(int n,int m)
{
	n/=k;
	m/=k;
	if(n>m) swap(n,m);
	int l,r;
	ll res=0;
	for(l=1;l<=n;l=r+1)
	{
		r=min(n/(n/l),m/(m/l));
		res=res+1ll*(n/l)*(m/l)*(sum[r]-sum[l-1]);
	}
	return res;
}
//--------------------------------------------------
int main()
{
	init(50000);
	int _;
	for(cin>>_;_;_--)
	{
		scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
		//容斥原理
		printf("%lld\n",f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,c-1));
	}
	return 0;
}