给定正整数a ≤ b和k，试求满足gcd（c，d）= k且c ≤ a，b ≤ d，c ≤ d二元组的个数。
gcd（c，d）= k，即gcd（c / k, d / k) = 1。
问题等价于k = 1时的情形。
如果我们枚举右区间内的数设为j，那么对应的右区间中的i满足（i，j）互质且i在1和min（b，j）之间。
若j≤b，则可直接用欧拉函数统计，
否则若j>b，考虑考虑【1，b】区间内不与j互质的数i，则i含有j中的素因子。
由容斥原理，假设j的素因子集合为 A = {p1,p2...pk}，那么【1，b】区间内与j不互质的数
N = （-1）#（S）* b / ∏（Si），其中S是A的子集。
可以用二进制法统计或则dfs：
设f（m）为左区间中不与j互质且含有j中最大素因子为pm的数个个数
则有N = sigma（f（m）），f（m）可以递归计算。
http://acm.hdu.edu.cn/showproblem.php?pid=1695
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 typedef __int64 LL; 6 const int maxn = 1e5 + 10; 7 int prime[maxn][20]; 8 LL phi[maxn]; 9 int a, b; 10 11 void init(){ 12 memset(phi, 0, sizeof phi); 13 phi[1] = 1; 14 for(int i = 2; i < maxn; i++){ 15 if(!phi[i]){ 16 for(int j = i; j < maxn; j += i){ 17 if(!phi[j]) phi[j] = j; 18 phi[j] -= phi[j] / i; 19 prime[j][++prime[j][0]] = i; 20 } 21 } 22 phi[i] += phi[i - 1]; 23 } 24 } 25 26 int dfs(int cur, int num, int u){ 27 int ans = 0; 28 for(int i = cur; i <= prime[u][0]; i++){ 29 int new_num = num / prime[u][i]; 30 ans += new_num - dfs(i + 1, new_num, u); 31 } 32 return ans; 33 } 34 35 void solve(){ 36 LL ans = phi[a]; 37 for(int i = a + 1; i <= b; i++) ans += a - dfs(1, a, i); 38 printf("%I64d ", ans); 39 } 40 41 int main(){ 42 //freopen("in.txt", "r", stdin); 43 init(); 44 int T; 45 scanf("%d", &T); 46 for(int i = 1, x, y, k; i <= T; i++){ 47 scanf("%d%d%d%d%d", &x, &a, &y, &b, &k); 48 printf("Case %d: ", i); 49 if(!k){ 50 puts("0"); 51 continue; 52 } 53 a /= k, b /= k; 54 if(a > b) swap(a, b); 55 solve(); 56 } 57 return 0; 58 }