本文主要是介绍【HDU】2204 Eddy's爱好 容斥原理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：【HDU】2204 Eddy's爱好
题目分析：首先，对于所有形如M^K的数我们都可以转化成M^(p1^k1 * p2^k2 * p3^k3 * ... )的形式，其中p1,p2,p3..为素数。则所有的M^K都可以转化成M'^p，其中p为素数。我们意识到2^60>10^18，所以只要求出前60以内的所有素数即可。然后，由于2*3*5*7>60，其中一个K的质因数最多只有三种。
令K'为每种质因数只有一个的数。
我们可以通过x = pow ( n , 1 / K' )求得指数为K'的数在[ 1 , n ]中出现的次数。
注意到可能存在x^p1 = y^p2（p1，p2为素数），那么我们就可以用容斥原理来去除重复。
则ans = sum { 指数为素数的个数x - 1 } - sum { 指数为两个质因数之积的个数x - 1 } + sum {指数为三个质因数之积的个数x - 1 } + 1。（x-1是因为不能包括这个数本身，否则K = 1不合题意；最后+1是因为还有个1）
这题精度要尤其注意。
代码如下：
#include <map>
#include <cmath>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std ;#define REP( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i )
#define FOR( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define REV( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define CLR( a , x ) memset ( a , x , sizeof a )
#define CPY( a , x ) memcpy ( a , x , sizeof a )typedef long long LL ;const double eps = 1e-8 ;int prime[20] = { 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 } ;LL n ;int dfs ( LL n , int cur , int num ) {int ans = 0 ;REP ( i , cur , 17 ) {int tmp = pow ( n , 1.0 / ( num * prime[i] ) ) + eps ;if ( pow ( 1.0 * tmp , 1.0 * num * prime[i] ) > n + eps ) -- tmp ;-- tmp ;if ( tmp <= 0 ) break ;ans += tmp - dfs ( n , i + 1 , num * prime[i] ) ;}return ans ;
}int main () {while ( ~scanf ( "%I64d" , &n ) ) printf ( "%d\n" , dfs ( n , 0 , 1 ) + 1 ) ;return 0 ;
}这篇关于【HDU】2204 Eddy's爱好 容斥原理的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
