JS's Blog
0%

Hdu 1695 - GCD (容斥)

Posted on Edited on In ,

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1695

题目大意：
给定区间[a,b][a,b]与区间[c,d][c,d]，求两区间内各取一数gcd为k的种数，a,b{a,b}与b,a{b,a}视为同一种

分析：
由于题目给定了一个特殊条件，a=c=1，所以其实转化为了求[1,b/k][1,b/k]与[1,d/k][1,d/k]内互质数对的个数
首先一个区间内与x互质的数的个数我们可以用容斥快速的求得，而区间又不是很大，所以可以直接暴力整个区间，求所有的互质数对

代码：

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
86
87
88
89
90
91
92
93
94
95
96
97
//#include<bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;

const ll mod = 1e9+7;

ll a,b,c,d,k;
const int maxn = 100000+10;
vector<int> ft[120005];
bool isprime[120000];

void init()
{
    for (int i = 2 ; i <= maxn ; i ++)
    {
        if (!isprime[i])
        {
            for (int j = i ; j <= maxn ; j += i)
            {
                isprime[j] = true;
                ft[j].push_back(i);
            }
        }
    }

}

ll solve(int x,int sta,ll n)
{
    int pos = 0;
    ll temp = 1;
    while (sta)
    {
        if (sta&1)
            temp *= ft[x][pos];
        pos ++;
        sta >>= 1;
    }

    return n/temp;
}



int main(){
    init();
    int T,t=1;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&k);
        printf("Case %d: ",t++);
        if (k==0)
        {
            printf("0\n");
            continue;
        }
        b/=k;d/=k;

        if (b*d==0)
            printf("0\n");
        else
        {
            if (b>d)
                swap(b,d);
            ll ans = 0;
            for (int i = 1 ; i <= d ; i ++)
            {
                ans += min(i*1LL,b);
                for (int j = 1 ; j < (1<<ft[i].size()); j ++)
                {
                    ll temp = solve(i,j,min(i*1LL,b));int cp = j,cnt = 0;
                    //printf("cp = %d\t",cp);
                    while (cp)
                    {
                        cp -= cp&(-cp);
                        cnt++;
                    }
                    //printf("cnt = %d\n",cnt);
                    if (cnt&1)  ans -= temp;
                    else    ans += temp;
                }
            }
            printf("%lld\n",ans);

        }

    }



    return 0;
}