题目大意：给你 a , b , c , d , k 五个值 （题目说明了 你可以认为 a=c=1） x 属于 [1,b] ，y属于[1,d] 让你求有多少对这样的 （x,y）满足gcd（x,y）==k。给你的时间是 3000 MS。 0 < a <= b <= 100,000, 0 < c <= d <= 100,000, 0 <= k <= 100,000
解题思路：因为 gcd（x,y）=k 那么，很显然 gcd（x / k,y / k）是等于 1 的（x,y 除了 k 一定没有其他的公因数）。那么，此时问题就可以转化为： x 属于 [1,b / k] ，y属于[1,d / k] 让你求有多少对这样的 （x,y）满足gcd（x,y）== 1 即x和y是互质的。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 100000;
//线性筛法求莫比乌斯函数
bool check[MAXN+10];
int prime[MAXN+10];
int mu[MAXN+10];
//递推
void mobius(ll mn)
{
mu[1]=1;
for(ll i=1;i<=mn;i++){
for(ll j=i+i;j<=mn;j+=i){
mu[j]-=mu[i];
}
}
}
int main()
{
ios::sync_with_stdio(false);
int n,a,b,d,c,k,bd,Case=1;
mobius(MAXN);
cin>>n;
while(n--)
{
cin>>a>>b>>c>>d>>k;
if(k==0){
printf("Case %d: 0
",Case++);
continue;
}
b=b/k;
d=d/k;
bd = min(b,d);
ll ans1=0,ans2=0;
for(int i=1;i<=bd;i++)
ans1+=(ll)mu[i]*(b/i)*(d/i);
for(int i=1;i<=bd;i++)
ans2+=(ll)mu[i]*(bd/i)*(bd/i);
ll ans = ans1-ans2/2;
printf("Case %d: %lld
",Case++,ans);
}
return 0;
}