推导一下
设
f
(
n
,
m
,
k
)
=
∑
i
=
1
n
∑
j
=
1
m
[
G
c
d
(
i
,
j
)
=
k
]
F
(
n
,
m
,
k
)
=
∑
i
=
1
n
∑
j
=
1
m
[
k
|
G
c
d
(
i
,
j
)
]
先不管
f
(
n
,
m
,
k
)
我们先化简
F
(
n
,
m
,
k
)
F
(
n
,
m
,
k
)
=
∑
i
=
1
n
k
∑
j
=
1
m
k
1
=
⌊
n
k
⌋
∗
⌊
m
k
⌋
轻松愉快
然后有
X
=
m
i
n
(
n
,
m
)
F
(
n
,
m
,
k
)
=
∑
n
k
|
x
X
f
(
n
,
m
,
n
k
)
∗
I
f
(
n
,
m
,
k
)
=
∑
i
=
1
⌊
X
k
⌋
F
(
n
,
m
,
i
k
)
∗
μ
(
i
k
)
f
(
n
,
m
,
k
)
=
∑
i
=
1
⌊
X
k
⌋
⌊
n
i
k
⌋
∗
⌊
m
i
k
⌋
∗
μ
(
i
k
)
于是 我们成功将
O
(
n
2
∗
T
)
变成了
O
(
n
∗
T
)
但是 还不够
观察下图
能够看到 许多的
⌊
n
i
k
⌋
⌊
m
i
k
⌋
都是相同的
于是 我们就想办法把相同的合并到一起
对于每一个
i
我们可以通过
⌊
m
⌊
m
i
k
⌋
⌋
求出 最后一个满足
⌊
m
i
k
⌋
相同的位置
同时
⌊
m
(
i
−
1
)
k
⌋
的位置我们记下了
那么当前的
⌊
m
i
k
⌋
的第一个位置即是 上一个位置+1
另外 凑巧的是 因为
⌊
n
i
k
⌋
⌊
m
i
k
⌋
的值一直相同
所以对于这一连串的
⌊
n
i
k
⌋
⌊
m
i
k
⌋
∗
μ
(
i
k
)
我们只需要求出
μ
(
i
k
)
的前缀和 就可以快速求出这一段的和了
(恐怕看完这一段你都不知道你一开始在求什么了)
附上理解代码
#include <iostream>
#include <cstdio>
#define LL long long
using namespace std;
inline int input()
{
char c=getchar();int o;bool f=0;
while(c>57||c<48)f|=(c=='-'),c=getchar();
for(o=0;c>47&&c<58;c=getchar())o=(o<<1)+(o<<3)+c-48;
return f?-o:o;
}
const int N=50123;
int mu[N],sum[N],prime[N],cnt=0;
bool mark[N];
void GetMu()
{
int num;
sum[1]=mu[1]=1;
for(int i=2;i<=50000;i++)
{
if(!mark[i]){mu[i]=-1,prime[++cnt]=i;}
for(int k=1;k<=cnt;k++)
{
num=i*prime[k];
if(num>N)break;
mark[num]=1;
if(i%prime[k]==0){mu[num]=0;break;}
else mu[num]=-mu[i];
}
sum[i]=sum[i-1]+mu[i];
}
}
int Cal(int a,int b)
{
if(a>b)swap(a,b);
int ans=0,pos;
for(int i=1;i<=a;i=pos+1)\\pos为上一个的末尾位置 当前+1
{
pos=min(a/(a/i),b/(b/i));\\要保证一连串都相同 所以取两者之中的更小值
ans+=(sum[pos]-sum[i-1])*(a/i)*(b/i);
}
return ans;
}
int main()
{
//freopen("In.txt","r",stdin);
GetMu();
int T=input(),a,b,c,d,k,res;
while(T--)
{
a=input();b=input();c=input();d=input();k=input();
a--;c--;
a/=k;b/=k;c/=k;d/=k;
res=Cal(a,c)+Cal(b,d)-Cal(a,d)-Cal(b,c);
printf("%d\n",res);
}
return 0;
}