学步园

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=526

http://acm.hdu.edu.cn/showproblem.php?pid=2204

题目的意思很是简单让你求1 - n( n <= 10^18)中能够表示成M^k(k > 1)的数有多少个。。

分析发现，我们知道，k不会太大，所以，我们完全可以枚举素次幂。。

为什么要枚举素次幂。。因为合数次幂一定会包含在素次幂中。

比如 如果8^4在范围内，那么64^2肯定是在范围内的。。所以我们只需要枚举素次幂的数就好。。

还有，需要用到容斥原理。为什么？

因为64 = 8^2 = 4^3 = 2^6。。。所以需要减去应该减去的那部分。。

需要注意的是，精度是时候需要注意一下。。不过还是比较给力的在nyoj上的数据，给力。

Code：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define INT long long

const int N = 20;
const double eps = 1e-8;
const INT prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};

INT _pow(INT a, INT k)
{
    INT ans = 1;
    while(k){
        if(k & 1) ans = ans * a;
        a = a * a;
        k = k >> 1;
    }
    return ans;
}
INT F(INT n, INT tmp)
{
    INT ans = pow((double)n, 1.0 / tmp) + eps;
    if(pow(ans, 0.0 + tmp) > n) ans --;
    if(ans < 1) ans = 1;
    return ans - 1;
}

INT solve(INT n)
{
    int p[N], top = 0;
    for(int i = 0; i < 20; i ++){
        if(_pow(2, prime[i]) <= n) p[top ++] = prime[i];
        else break;
    }
    INT ans = 0;
    for(int i = 1; i < (1 << top); i ++){
        int cnt = 0;
        INT tmp = 1;
        for(int j = 0; j < top; j ++){
            if(i & (1 << j)){
                cnt ++;
                tmp = tmp * p[j];
            }
        }
        if(cnt % 2) ans += F(n, tmp);
        else ans -= F(n, tmp);
    }
    return ans;
}

int main()//64
{
//    freopen("1.txt", "r", stdin);
    INT n;
    while(cin >> n){
        cout << solve(n) + 1 << endl;
    }
    return 0;
}

----->

容斥原理。2进制写法很是给力。。只不过，这种应该只针对小数据吧。。。