hdu 1695 GCD(莫比乌斯反演)

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

2008 “Sunline Cup” National Invitational Contest

题意:  给你5个整数 a , b , c , d , k ,要你在[a,b]中找到一个x,在[c,d]中找到一个y,使得gcd(x,y)=k(注意 gcd(x,y)=k,与gcd(y,x)=k算作同一种足组合,虽然x,y的取值范围不同)。要你求出总共有多少种组合。

分析:   对于gcd(x,y)=k;

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

但是这样依旧会tle到天上去......,怎么办?

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

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

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

3457
来自专栏小樱的经验随笔

HDU 2504 又见GCD(最大公约数与最小公倍数变形题)

又见GCD Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

2913
来自专栏ml

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
来自专栏ml

HDUOJ---1171

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

2876
来自专栏ml

HDUOJ ---1423 Greatest Common Increasing Subsequence(LCS)

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

2905
来自专栏ml

HDUOJ--4565 So Easy!

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

36113
来自专栏ml

专题练习---(数论)莫比乌斯反演

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

37211

扫码关注云+社区

领取腾讯云代金券