JS's Blog
0%

Hdu 2204 - Eddy's爱好（容斥）

Posted on Edited on In ,

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

题目大意：
给定一个数N，求1-N内有多少个数可以表示成MKM^K的形式，其中K>1

分析：
可以枚举指数进行容斥，指数最多63次，263>10182^{63}>10^{18}，然后对于含有奇数个质因子的指数加入，含有偶数个的减去，对于含有重复质因子的指数会被其他更小的指数覆盖，不用考虑

当前寻找的指数为k,也就是要找最大的满足$a^k\leq n $的数，由于上界为101810^{18}，所以在求aka^k的过程中很容易就会爆long long ，所以最好再加个限制，由于没想到什么好的办法，我打了一个表来加上限制

代码：

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
//#include<bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;

const ll mod = 1e9+7;

int up[100];

ll n;

int divide(int x)
{
    int cnt =0;
    for (int i = 2 ; i *i <= x ; i ++)
    {
        if (x%i==0)
        {
            cnt++;
            x /= i;
            if (x%i==0)
                return -1;
        }
    }
    if (x!=1)
        cnt++;
    return cnt;
}

void init()
{
    up[2] = 1000000000;
    up[3] = 1000000;
    up[5] = 3981;
    up[6] = 1000;
    up[7] = 372;
    up[10] = 63;
    up[11] = 43;
    up[13] = 24;
    up[14] = 19;
    up[15] = 15;// 437893890380859375
    up[17] = 11;// 505447028499293771
    up[19] = 8;// 144115188075855872
    up[21] = 7;// -1261475310744950487
    up[22] = 6;// 131621703842267136
    up[23] = 6 ;//789730223053602816
    up[26] = 4;// 4503599627370496
    up[29] = 4;// 288230376151711744
    up[30] = 3 ;//205891132094649
    up[31] = 3 ;//617673396283947
    up[33] = 3 ;//-2080022246165795451
    up[34] = 3 ;//0
    up[35] = 3 ;//0
    up[37] = 3 ;//-8741818693953543755
    up[38] = 2 ;//274877906944
    up[39] = 2 ;//549755813888
    up[41] = 2;// 0
    up[42] = 2 ;//0
    up[43] = 2 ;//0
    up[46] = 2 ;//70368744177664
    up[47] = 2 ;//140737488355328
    up[51] = 2;// 0
    up[53] = 2 ;//0
    up[55] = 2 ;//0
    up[57] = 2;// 144115188075855872
    up[58] = 2 ;//288230376151711744
    up[59] = 2 ;//0
}


ll quickpow(ll a, ll n)
{
    ll res= 1;
    while (n)
    {
        if (n&1)    res= res*a;
        a = a*a;
        n >>=1;
    }
    return res;
}


ll solve(ll x)
{
    ll rt = (ll)pow(n*1.0,1.0/x);
    if (quickpow(rt,x)<=n)
    {
        while (quickpow(rt+1,x)<=n&&rt+1<=up[x])
            rt ++;
    }
    else
    {
        while (quickpow(rt,x)>n)
            rt--;
    }
    return rt-1;
}

int main(){
    init();
    int T,t=1;
    while (~scanf("%lld",&n))
    {
        ll ans = 0;
        for (int i = 2 ; i <= 63 ; i ++)
        {
            if (quickpow(2,i)>n)
                break;
            int cnt = divide(i);
            if (cnt==-1) continue;
            if (cnt&1)  ans += solve(i);
            else ans -= solve(i);
        }
        printf("%lld\n",ans+1);

    }



    return 0;
}