HDu 1695—GCD(2つの区間の内で互いに質の数の対数を求めます)
3453 ワード
タイトルリンク:転送ゲート
GCD
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 11844 Accepted Submission(s): 4465
Problem Description
Given 5 integers: a, b, c, d, k, you're to find x in a...b, y in c...d that GCD(x, y) = k. GCD(x, y) means the greatest common divisor of x and y. Since the number of choices may be very large, you're only required to output the total number of different number pairs.
Please notice that, (x=5, y=7) and (x=7, y=5) are considered to be the same.
Yoiu can assume that a = c = 1 in all test cases.
Input
The input consists of several test cases. The first line of the input is the number of the cases. There are no more than 3,000 cases.
Each case contains five integers: a, b, c, d, k, 0 < a <= b <= 100,000, 0 < c <= d <= 100,000, 0 <= k <= 100,000, as described above.
Output
For each test case, print the number of choices. Use the format in the example.
Sample Input
GCD
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 11844 Accepted Submission(s): 4465
Problem Description
Given 5 integers: a, b, c, d, k, you're to find x in a...b, y in c...d that GCD(x, y) = k. GCD(x, y) means the greatest common divisor of x and y. Since the number of choices may be very large, you're only required to output the total number of different number pairs.
Please notice that, (x=5, y=7) and (x=7, y=5) are considered to be the same.
Yoiu can assume that a = c = 1 in all test cases.
Input
The input consists of several test cases. The first line of the input is the number of the cases. There are no more than 3,000 cases.
Each case contains five integers: a, b, c, d, k, 0 < a <= b <= 100,000, 0 < c <= d <= 100,000, 0 <= k <= 100,000, as described above.
Output
For each test case, print the number of choices. Use the format in the example.
Sample Input
21 3 1 5 11 11014 1 14409 9
Sample Output
Case 1: 9Case 2: 736427HintFor 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).
解题思路：求两个区间内gcd(x,y) = k,那么x/k与y/k互质，即求区间[1,b/k]与[1,d/k]内有多少对数互质,可以先求一个数与某个区间互质的数的个数。
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N = 100300;
const int INF = 0x3f3f3f3f;
int solve(int n,int r){
vectorp;
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 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
",++cas,sum);
}
return 0;
}