GCD
Time Limit : 6000/3000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 0 Accepted Submission(s) : 0
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.<br>Please notice that, (x=5, y=7) and (x=7, y=5) are considered to be the same.<br><br><b>Yoiu can assume that a = c = 1 in all test cases.</b><br>
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.<br>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.<br>
Output
For each test case, print the number of choices. Use the format in the example.<br>
Sample Input
2<br>1 3 1 5 1<br>1 11014 1 14409 9<br>
Sample Output
Case 1: 9<br>Case 2: 736427<br><br><div style='font-family:Times New Roman;font-size:14px;background-color:F4FBFF;border:#B7CBFF 1px dashed;padding:6px'><div style='font-family:Arial;font-weight:bold;color:#7CA9ED;border-bottom:#B7CBFF 1px dashed'><i>Hint</i></div>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).</div>
Source
2008 ”°Sunline Cup”± National Invitational Contest