题目大意：已知 1 <= x <= b , 1 <= y <= d , 求 gcd ( x , y ) = k 的对数。请注意，（x=5， y=7） 和 （x=7， y=5） 被认为是相同的。
思路：先将 gcd ( x , y ) = k 两边同时除以 k ，得到 gcd ( x / k , y / k ) = 1，这时问题就变成了 1 <= x <= b / k , 1 <= y <= d / k ，x 和 y 互质的对数（保证 x <= y ）。
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
const int N=1e5+5;
int vis[N];
vector<int> v[N];//存每个数的质因子
void init(){//预处理，将每个数的质因子求出来
for(int i=2;i<=1e5;i+=2) v[i].push_back(2);
for(int i=3;i<=1e5;i+=2){
if(!vis[i]){
for(int j=i;j<=1e5;j+=i){
vis[j]=1;
v[j].push_back(i);
}
}
}
}
int fun(int n,int m){//找出 1 ~ n 中与 m 不互质的数 （容斥原理）
int sum=0;
for(int i=1;i<(1<<v[m].size());i++){
int cnt=0,num=1;
for(int j=0;j<v[m].size();j++){
if(i&(1<<j)) cnt++,num*=v[m][j];
}
if(cnt&1) sum+=n/num;
else sum-=n/num;
}
return sum;
}
signed main(){
IOS
init();
int _;
cin >> _;
for(int t=1;t<=_;t++){
int a,b,c,d,k,ans=0;
cin >> a >> b >> c >> d >> k;
if(k==0) cout << "Case " << t << ": 0" << endl;//k=0时要特判
else{
b/=k,d/=k;
if(b>d) swap(b,d);//保证 b < d
for(int i=1;i<=d;i++){
if(i<=b) ans=ans+i-fun(i,i);
else ans=ans+b-fun(b,i);
}
cout << "Case " << t << ": " << ans << endl;
}
}
return 0;
}