1695：GCD

题目描述

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.

输入解释

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.

输出解释

For each test case, print the number of choices. Use the format in the example.

输入样例

2
1 3 1 5 1
1 11014 1 14409 9

输出样例

Case 1: 9
Case 2: 736427

提示

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

来自杭电HDUOJ的附加信息

Recommend

wangye

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2008 “Sunline Cup” National Invitational Contest

源链接： HDU-1695

最后修改于 2020-10-25T22:47:17+00:00 由爬虫自动更新

共提交 4 次

通过率 0.0%

时间上限	内存上限
6000/3000MS(Java/Others)	32768/32768K(Java/Others)