HDU-1695 GCD(莫比乌斯反演)

冷不防 2022-06-10 12:15 179阅读 0赞

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

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

题意：给你a,b,c,d,k，求满足gcd(x,y)=k，a<=x<=b，c<=y<=d，的x和y一共有多少对，(2,1)和(1,2)算一种。

思路：这道题可以用容斥原理去做，也可以用莫比乌斯反演做，用莫比乌斯反演去做的话，这是一道非常好的莫比乌斯反演入门题。有一篇博客讲得非常好，传送门→http://blog.csdn.net/lixuepeng\_001/article/details/50577932

对于一道题，想用莫比乌斯反演去解决，最关键的就是设出F(d)和f(d)这两个方程，且这两个方程要有倍数关系或约数关系。这道题我们可以设F(d)为有多少对(x,y)满足 gcd(x,y)== d 的倍数，f(d)为有多少对(x,y)满足 gcd(x,y)== d ，这样我们就可以通过莫比乌斯反演根据F(d)很快求出f(d)。这道题还要注意一下去重。AC代码如下：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    #include <set>
    #include <functional>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 100005;
    const int MOD = 1000000007;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    
    bool vis[MAXN];
    int primes[MAXN];
    int miu[MAXN];
    
    void calc(int limit)
    {
    	memset(vis, false, sizeof(vis));
    	memset(miu, 0, sizeof(miu));
    	int tot = 0;
    	miu[1] = 1;   //根据定义，μ(1) = 1  
    	for (int i = 2; i <= limit; i++)
    	{
    		if (!vis[i])  //未发现的质数  
    		{
    			primes[tot++] = i;
    			miu[i] = -1;
    			//质数，除了1以外，只有它自己是自己的质因数  
    			//因此根据定义，μ(i) = (-1)^1 = -1  
    		}
    		for (int j = 0; j < tot; j++)
    		{
    			int k = i*primes[j];
    			if (k > limit)break;
    			vis[k] = true;
    			if (i % primes[j]) //i不是primes[j]的整数倍时，i*primes[j]就不会包含相同质因子。  
    				miu[k] = -miu[i];     //此时根据其积性函数的特性得 miu[k] = miu[i]*miu[primes[j]]，因为primes[j]是质数，miu值为-1  
    			else                      //然后化简得miu[k] = -miu[i]; (perfect!)  
    				break;
    		}
    	}
    }
    
    int main()
    {
    	calc(100003);
    	int a, b, c, d, k;
    	int T;
    	LL ans;
    	LL res;
    	scanf("%d", &T);
    	for (int CAS = 1; CAS <= T; CAS++)
    	{
    		scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
    		if (k == 0)
    		{
    			printf("Case %d: 0\n", CAS);
    			continue;
    		}
    		b /= k;
    		d /= k;
    		ans = 0;
    		res = 0;
    		for (int i = 1; i <= min(b,d); i++)
    		{
    			ans += (long long)miu[i] * (b / i)*(d / i);
    			res += (long long)miu[i] * (min(b, d) / i)*(min(b, d) / i);
    		}
    		ans -= res / 2;
    		printf("Case %d: %lld\n",CAS, ans);
    	}
    }