hdu1695—GCD（求两个区间内互质的数的对数）
题目链接：传送门
GCD
运行时限制：每秒允许执行的循环次数为6,000次（Java和其他语言版本）；内存使用限制：最大可用内存空间为32,768 KB（Java和其他语言版本）。
总提交数量：11,844；已通过的数量：4,465。
Problem Description
Provided that there are five integers named a through d and k,the task is to determine the pair (x,y) where x ranges from a to b and y ranges from c to d such that their greatest common divisor equals k. The greatest common divisor of two numbers refers specifically to their largest shared factor. Due to the potentially enormous number of possible combinations it's only necessary for you to calculate and report the total count of distinct integer pairs. The pair (5 7) should be regarded identical to (7 5).
Yoiu can assume that a = c = 1 in all test cases.
Input
包含多组测试用例的输入文件中第一行给出测试用例的数量（不超过3千组）。每组测试用例包含五个整数a、b、c、d和k（满足以下条件：），如前所述。
Output
In every test case, output the number of options. The output should follow the pattern shown in the example.
Sample Input
21 3 1 5 11 11014 1 14409 9
Sample Output
Case 1: 9Case 2: 736427
Hint
For the first sample input, all the 9 pairs of numbers are (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5).
解决思路：寻找x和y在两个区间内满足gcd(x,y)=k的情况，则x除以k所得的结果与y除以k所得的结果必须互质；换句话说，在新的范围内寻找满足条件的数字对的数量即可；这可以通过计算特定范围内的互质数字对来实现
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 100300;
const int INF = 0x3f3f3f3f;
int solve(int n,int r){
vector<int>p;
for(int i=2; i*i<=n; ++i)
if(n%i == 0){
p.push_back (i);
while(n%i == 0)
n /= i;
}
if(n > 1)
p.push_back(n);
int sz = p.size();
int sum = 0;
for(int i=1; i<(1<<sz); ++i){
int mult = 1,bits = 0;
for (int j=0; j<sz; ++j)
if (i&(1<<j)) {
++bits;
mult *= (ll)p[j];
}
int cur = r/mult;
if (bits % 2 == 1) sum += cur;
else sum -= cur;
}
return r - sum;
}
int main()
{
int T,cas = 0;
scanf("%d",&T);
while( T-- ){
int a,b,c,d,k;
scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
if(k == 0) {printf("Case %d: %d\n",++cas,0);continue;}
int t1 = b/k;
int t2 = d/k;
if( t1 > t2 ) swap(t1,t2);
ll sum = 0;
for( int i = 1 ; i <= t1 ; ++i ) sum += (ll)solve(i,t1);
sum++; sum /= 2;
for( int i = t1+1 ; i <= t2 ; ++i ) sum += (ll)solve(i,t1);
printf("Case %d: %lld\n",++cas,sum);
}
return 0;
}