MYF

HDU 1695 GCD

Posted on | In | | Visitors

题目链接

HDU 1695

解题方法：莫比乌斯反演

题目分析

题目大意

给出a, b, c, d, k，求1<=x<=b, 1<=y<=d范围内有多少组(x, y)满足gcd(x, y) == k

解析

先了解一下莫比乌斯公式的两种表达形式：

其中mu[]我们可以通过筛法求出。

我们分析一下这个问题，如果要找gcd为k的解，我们可以把区间先缩短为原来的1/k，那么，我们只需要找1<=x<=b/k, 1<=y<=d/k范围内有多少组(x, y)满足gcd(x, y) == 1的解。

然后就是莫比乌斯反演的解决方法了。

我们可以先找到一个大范围F(n)表示满足对于(x, y)，n|gcd(x, y)，也就是说，gcd(x, y)可以是n, 2n, 3n, 4n, ...，根据区间，我们很容易发现F(n) = (b/n)*(d/n)。然后我们可以找到一个小范围f(n)表示满足对于(x, y)，n=gcd(x, y)，也就是说，gcd(x, y)只能是n。至此，我们可以发现我们应该应用莫比乌斯公式的第二种表现形式，由于我们已经把区间整体处以k了，所以我们只需要找1<=x<=b/k, 1<=y<=d/k范围内的f(1)，即为解。然后我们根据f(n)的计算公式，枚举d从1~min(b/k, d/k)，求出∑mu(d)F(d)即可。

最后还有一点值得注意的，对于n<m，我们求的实际上是(1, n)区间和(1, m)中的对数，但是在(1, n)和(1, n)中会产生一些重复的，比如q<p<n<m，那么我们对于第一个区间计算(q, p)时，已经计算了一遍(q, p)又计算了一遍(p, q)，但是如果q<n<p<m，我们只会计算一遍(q, p)。所以我们要把重复的部分删掉，即mobius(n, n)／2对情况。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <iostream>
#include <iosfwd>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1.0)
#define PB push_back
#define MP make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define debug2(x,y) cout<<"Debug : ---"<<x<<" , "<<y<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int maxn=100000+5;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
int vis[maxn];
ll mu[maxn];
int prime[maxn];
int cnt;
void Init()
{
    memset(vis,0,sizeof(vis));
    mu[1] = 1;
    cnt = 0;
    for(int i=2; i<maxn; i++)
    {
        if(!vis[i])
        {
            prime[cnt++] = i;
            mu[i] = -1;
        }
        for(int j=0; j<cnt&&i*prime[j]<maxn; j++)
        {
            vis[i*prime[j]] = 1;
            if(i%prime[j]) mu[i*prime[j]] = -mu[i];
            else
            {
                mu[i*prime[j]] = 0;
                break;
            }
        }
    }
}
ll mobius(ll n,ll m){
    ll ans = 0;
    for (int i=1; i<=n; i++) {
        ans += mu[i] * (n/i) * (m/i);
    }
    return ans;
}
int main(){
    Init();
    int T;
    scanf("%d",&T);
    for (int cas = 1 ; cas <= T; cas ++) {
        int a,b,c,d,k;
        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;
        if (b > d) swap(b, d);
        
        printf("Case %d: %lld\n",cas, mobius(b,d) - mobius(b,b)/2);
    }
}