题目
题目大意
给出a,b,c,d,k,求出a<=x<=b, c<=y<=d 且gcd(x,y) == k 的（x,y）的对数。
Input
样例个数T (T <= 3000) 每个样例输入a,b,c,d,k，保证所有的a和c都等于1. (a==1 , c==1 , 0 < b,d <= 100,000 , 0 <= k <= 100,000)
Output
对于每个样例，输出其对应的答案。
Sample Input
2
1 3 1 5 1
1 11014 1 14409 9
Sample Output
Case 1: 9
Case 2: 736427
Hint
样例一 (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5).
题解
题目要求：$\sum_{i=1}^{b}\sum_{j=1}^{d}[\gcd(i,j)==k]$
先不考虑去重，设$f(x)=\sum_{i=1}^{b}\sum_{j=1}^{d}[\gcd(i,j)==x]$
$F(x)=\sum_{x\vert d}f(d)=\left\lfloor\frac{b}{x}\right\rfloor\left\lfloor\frac{d}{x}\right\rfloor$
则$f(x)=\sum_{x\vert d}\mu(\frac{d}{x})F(d)=\sum_{i=1}^{min(b,d)}\mu(i)\left\lfloor\frac{b}{ix}\right\rfloor\left\lfloor\frac{d}{ix}\right\rfloor$
这个可以用整除分块搞了
现在因为要去重，发现重的部分都在$min(b,d)$里，所以在求一下$\sum_{i=1}^{min(b,d)}\sum_{j=1}^{min(b,d)}[\gcd(i,j)==k]$的答案$ans1$，
则重复部分为$\frac{ans1-1}{2}$（$-1$是$x=k,y=k$的情况），减去即可
PS:注意有$k=0$的情况…原来没看见于是一直RE QAQ
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=1e5+1;
int t,a,b,c,d,k,tot,cnt;
int pm[MAX],u[MAX];
bool use[MAX];
int main()
{
u[1]=1;
for(int i=2;i<MAX;++i)
{
if(!use[i]) pm[++tot]=i,u[i]=-1;
for(int j=1;j<=tot&&i*pm[j]<MAX;++j)
{
use[i*pm[j]]=1;
if(i%pm[j]==0)
{
u[i*pm[j]]=0;
break;
}
u[i*pm[j]]=-u[i];
}
}
for(int i=1;i<MAX;++i)
u[i]+=u[i-1];
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
if(!k||k>max(b,d))
{
printf("Case %d: %d\n",++cnt,0);
continue;
}
if(b>d) swap(b,d);
LL ans=0,ans1=0;
for(int l=1,r;l<=b;l=r+1)
r=min(b/(b/l),d/(d/l)),ans+=1ll*(b/(l*k))*(d/(l*k))*(u[r]-u[l-1]);
for(int l=1,r;l<=b;l=r+1)
r=b/(b/l),ans1+=1ll*(b/(l*k))*(b/(l*k))*(u[r]-u[l-1]);
printf("Case %d: %lld\n",++cnt,ans-(ans1-1)/2);
}
return 0;
}
