原题：点击打开链接
题意很明确了，即：给你一个正整数N，确定在1到N之间有多少个可以表示成M^K（K>1)的数。
本题目为容斥原理题目，容斥原理的伪代码如下：
1void dfs(int cur , int cmn, int id) 2{ 3 1.计算当前集合|cmn|的个数; 4 2.判断id的奇偶，以此判定+或者-， 此处id的判断方法可用(id & 1)位运算来判断; 5 3.dfs(cur+1, 重复集合, id + 1); 例子：如果之前计算了p(a),p(b), 即计算p(a)+p(b)-p(a交b); 6}
姑且这么解释，希望读者能够看懂。
分析本题：
如何避免重复计算：
1.即M的次方为质数。K如果是质数，就不能拆分成为两个数的乘积，减少了部分重复;
2.还有一种重复是类似与4 ^3 与 8 ^ 2的重复(对于容斥来讲，就是2 ^ (2*3)，这种重复就得利用容斥原理清除。
3.离散数学学得好的可以用代数系统考虑。
特殊知识：pow（n， 1 / num）可以用于开方。
1//============================================================================ 2// Name : hdu2204.cpp 3// Author : 4// Version : 5// Copyright : Your copyright notice 6// Description : Hello World in C++, Ansi-style 7//============================================================================ 8 9#include <iostream> 10#include <stdio.h> 11#include <string.h> 12#include <math.h> 13using namespace std; 14#define lln long long int 15 16lln prime[20] = {2, 3, 5, 7, 11, 13, 17, 19 ,23, 29, 31, 37, 41, 43, 47, 53, 57,59 ,61};//打表质数，因为2 ^60次方 > 10 ^18 17lln ans, tmp, n; 18 19 20void dfs(int cur, int cmn, int id){ 21 if(id >= 4)//2 ^ (2 * 5 * 7 = 70 ) 22 return; 23 lln num, i; 24 for(i = cur; i < 19; i++){ 25 num = (lln) pow(n, 1 / (prime[i] * cmn)); //find the same key; pow a ^(1/n) 学到了。 26 if(id & 1) // id odd, minus or add 27 ans += num; 28 else 29 ans -= num; 30 dfs(i+1, cmn * prime[i], id+1); 31 //find other 32 } 33} 34 35 36void ace(){ 37 while (cin >> n) { 38 ans = 0; 39 dfs(0, 1, 1); 40 printf("%I64d\n", ans); 41 } 42} 43 44int main() { 45 ace(); 46 return 0; 47}