hdu2204 Eddy's爱好

原题：点击打开链接

题意很明确了，即：给你一个正整数N，确定在1到N之间有多少个可以表示成M^K（K>1)的数。

本题目为容斥原理题目，容斥原理的伪代码如下：

void dfs(int cur , int cmn, int id)
{
    1.计算当前集合|cmn|的个数;
    2.判断id的奇偶，以此判定+或者-， 此处id的判断方法可用(id & 1)位运算来判断;
    3.dfs(cur+1, 重复集合, id + 1); 例子：如果之前计算了p(a),p(b), 即计算p(a)+p(b)-p(a交b);
}

分析本题：

如何避免重复计算：

1.即M的次方为质数。K如果是质数，就不能拆分成为两个数的乘积，减少了部分重复;

2.还有一种重复是类似与4 ^3 与 8 ^ 2的重复(对于容斥来讲，就是2 ^ (2*3)，这种重复就得利用容斥原理清除。

3.离散数学学得好的可以用代数系统考虑。

特殊知识：pow（n， 1 / num）可以用于开方。

//============================================================================
// Name        : hdu2204.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; #define lln long long int lln 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 lln ans, tmp, n; void dfs(int cur, int cmn, int id){ if(id >= 4)//2 ^ (2 * 5 * 7 = 70 ) return; lln num, i; for(i = cur; i < 19; i++){ num = (lln) pow(n, 1 / (prime[i] * cmn)); //find the same key; pow a ^(1/n) 学到了。 if(id & 1) // id odd, minus or add ans += num; else ans -= num; dfs(i+1, cmn * prime[i], id+1); //find other } } void ace(){ while (cin >> n) { ans = 0; dfs(0, 1, 1); printf("%I64d\n", ans); } } int main() { ace(); return 0; }