給你 a , b , c , d , k 五個值 （題目說明了 你可以認為 a=c=1） ，是以 x 屬于 [1,b] ，y屬于[1,d] 讓你求有多少對這樣的 （x,y）滿足gcd（x,y）==k。
首先 ，這道題可以進行簡化，因為 gcd（x,y）=k， 那麼，很顯然 gcd（x / k,y / k）是等于 1 的。那麼，此時問題就可以轉化為： x 屬于 [1,b / k] ，y屬于[1,d / k] ，讓你求有多少對這樣的 （x,y）滿足gcd（x,y）== 1 ，即x和y是互質的。 我們需要用到莫比烏斯反演（當然容斥定理也可以），先來看一下什麼是莫比烏斯反演。
這裡先給出莫比烏斯的兩個公式 ：
這兩個就是莫比烏斯反演的兩種表現形式
反演的核心所在是莫比烏斯函數，什麼是莫比烏斯函數呢？ 我們在下面給出它的定義：
它就是莫比烏斯函數，我們稱之為 mu 函數，也是整個反演最為重要的部分。
現在我們來繼續解決上面的那個問題。如何去求有多少對這樣的 （x,y）滿足gcd（x,y）== 1 。這個問題你直接拿到手發現确實比較麻煩，但是換個思路，如果我們去求有多少對這樣的 （x,y）滿足 gcd（x,y）== 1 的倍數 呢？ 是不是就非常簡單了呢？
我們設：
F[i] 為有多少對（x,y）滿足 gcd（x,y）== i 的倍數
f[i] 為有多少對（x,y）滿足 gcd（x,y）== i
F[i] 很容易求出是 F[i]=b/i*d/i
是以我們需要解決的問題，就是如何求出 f[1]
根據
公式你可以發現，在你對函數進行構造時是需要滿足反演對函數的要求的，這個需要你自己來體會，至于另一個公式的構造方法是 “約數” 的關系，而這個則是 “倍數” 的關系。
我們很容易得到 F[i]=f[i] + f[i2] + f[i3]+…
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=100000+100;
int mu[maxn];
bool isprime[maxn];
int prime[maxn],tot;
void init(){
for(int i=0;i<maxn;i++) isprime[i]=true;
isprime[0]=isprime[1]=false;
tot=0;
mu[1]=1;
for(int i=2;i<maxn;i++){
if(isprime[i]) prime[tot++]=i,mu[i]=-1;
for(int j=0;j<tot && i*prime[j]<maxn;j++){
isprime[i*prime[j]]=false;
if(i%prime[j]) mu[i*prime[j]]=-mu[i];
else break;
}
}
}
inline ll Mobius(int a,int b){
ll res=0;
for(int i=1;i<=a;i++) res+=(ll)mu[i]*(a/i)*(b/i);
ll tmp=0;
for(int i=1;i<=a;i++) tmp+=(ll)mu[i]*(a/i)*(a/i);
return res-tmp/2;
}
int main(){
int T,C=0;
init();
scanf("%d",&T);
while(T--){
int a,b,c,d,k;
scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
if(k==0){
printf("Case %d: 0\n",++C);
continue;
}
b/=k;
d/=k;
if(b>d) swap(b,d);
printf("Case %d: %lld\n",++C,Mobius(b,d));
}
}