# GCD

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 6081    Accepted Submission(s): 2223

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

2 1 3 1 5 1 1 11014 1 14409 9

Sample Output

Case 1: 9

Case 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).

Source

常规的化简就是 gcd(x/k,y/k)=1;  --->即【a,b】范围缩减到--》【a/k,b/k】，同理[c,d] 缩减到-->[c/k,d/k];

还需要优化.  这时候就需要用到容斥原理了。

0 条评论

## 相关文章

### HDU 1005 Number Sequence【多解，暴力打表，鸽巢原理】

Number Sequence Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32...

3457

2913

### HDUOJ-------2493Timer(数学 2008北京现场赛H题)

Timer Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

2684

### POJ 1655 Balancing Act【树的重心】

Balancing Act Time Limit: 1000MS Memory Limit: 65536K Total Submissions:...

2816

### POJ2409 Let it Bead(Polya定理)

"Let it Bead" company is located upstairs at 700 Cannery Row in Monterey, CA. As...

1042

### HDU 1711 Number Sequence(KMP裸题，板子题，有坑点)

Number Sequence Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/3...

3114

### HDUOJ---1171

http://acm.hdu.edu.cn/showproblem.php?pid=1171 Big Event in HDU Time Limit: 1000...

2876

### HDUOJ ---1423 Greatest Common Increasing Subsequence（LCS）

Greatest Common Increasing Subsequence Time Limit: 2000/1000 MS (Java/Others)   ...

2905

### HDUOJ--4565 So Easy!

So Easy! Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (...

36113

### 专题练习---（数论）莫比乌斯反演

GCD Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32...

37211 