题目链接：
?pid=1695
题目大意：
给你5个整数a、b、c、d、k，在区间[a，b]中选一个数x，在区间[c，d]中选一个数y，使得x和y的
公约数为k，即gcd(x，，y) = k。现在问题来了：这样的整数对共有多少对。
思路：
题目假定a = c = 1，那么区间就变为了[1，b]和[1，d]。求gcd(x，y) = k，其实可以将区间端点除以
k，得到[1，b/k]和[1，d/k]。问题就变为了[1，b/k]和[1，d/k]中共有多少互素的整数对。
由于b可能大于d，为了方便，我们令d > b，不满足则交换d和b。
我们可以固定较小的区间[1，b/k]， 用i遍历另一个区间[1，d/k]。
当i <= b/k时，可以很容易看出，求i与[1，b/k]中互质的数的对数就是求i的欧拉函数，累加起来就是结果。
当i > b/k时，就变为了和HDU4135、HDU2841类似的问题，用容斥定理来求。
AC代码：
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#define LL __int64using namespace std;LL Q[100010],factor[110000],num;LL Prime[100010],phi[100010];bool UnPrime[100010];void Euler(){int k = 0;phi[1] = 1;for(int i = 2; i <= 100000; ++i){if(!UnPrime[i]){Prime[k++] = i;phi[i] = i-1;}for(int j = 0; j < k && Prime[j]*i <= 100000; ++j){UnPrime[Prime[j]*i] = true;if(i % Prime[j] != 0){phi[Prime[j]*i] = phi[i]*(Prime[j]-1);}else{phi[Prime[j]*i] = phi[i]*Prime[j];break;}}}for(int i = 2; i <= 100000; ++i)phi[i] += phi[i-1];}void Divid(LL n){num = 0;for(LL i = 2; i*i <= n; ++i){if(n%i==0){while(n%i==0){n /= i;}factor[num++] = i;}}if(n != 1)factor[num++] = n;}LL solve(LL n) //»¥³â¶¨Àí{LL k,t,ans;t = ans = 0;Q[t++] = -1;for(LL i = 0; i < num; ++i){k = t;for(LL j = 0; j < k; ++j)Q[t++] = -1*Q[j]*factor[i];}for(LL i = 1; i < t; ++i)ans += n/Q[i];return ans;}int main(){int T,kase = 0;Euler();scanf("%d",&T);while(T–){LL a,b,c,d,k,ans;scanf("%I64d %I64d %I64d %I64d %I64d",&a,&b,&c,&d,&k);if(k == 0){printf("Case %d: 0\n",++kase);continue;}if(b > d)swap(b,d);b /= k;d /= k;ans = phi[b];for(LL i = b+1; i <= d; ++i){Divid(i);ans += (b – solve(b));}printf("Case %d: %I64d\n",++kase,ans);}return 0;}
也和他共度。甚至连吵架也是重复的，
