HDU-1695 GCD

题目大意：已知 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(){IOSinit();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;
}