题目链接：
BZOJ 2301 Problem B
题意:
区间 x∈[a,b],y∈[c,d]满足gcd(x,y)=k的(x,y)的有序对数
分析：
莫比乌斯反演+优化。
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <bitset>
using namespace std;
const int MAX_N = 50010;
typedef long long ll;bitset<MAX_N> bs;
int prime_cnt, prime[MAX_N];
ll mu[MAX_N], sum[MAX_N];void GetMu()
{bs.set();prime_cnt = 0;memset(mu, 0, sizeof(mu));mu[1] = 1;for(int i = 2; i < MAX_N; ++i) {if(bs[i] == 1){mu[i] = -1; prime[prime_cnt++] = i;}for(int j = 0; j < prime_cnt && i * prime[j] < MAX_N; ++j) {bs[i* prime[j]] = 0;if(i % prime[j]) {mu[i * prime[j]] = -mu[i]; }else {mu[i * prime[j]] = 0;break;}}}for(int i = 1; i < MAX_N; ++i) {sum[i] = sum[i - 1] + mu[i];}
}ll solve(int n, int m)//计算[1,n]和[1,m]区间有多少有序对(x, y)使得gcd(x,y) = 1
{ll ans = 0;int top = min(n, m), last;for(int i = 1; i <= top; ++i) {last = min(n / (n / i), m / (m / i));ans += (ll) (n / i) * (m / i) * (sum[last] - sum[i - 1]);i = last;}return ans;
}int main()
{GetMu();int T, a, b, c, d, k;scanf("%d", &T);while(T--) {scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);if(k == 0){printf("0\n");continue;}ll ans = solve(b / k, d / k) + solve((a - 1) / k, (c - 1) / k) - solve((a - 1) / k, d / k) - solve((c - 1) / k, b / k);printf("%lld\n", ans);}return 0;
}