首页 > 代码库 > HDU 2204 Eddy's爱好（容斥原理）

HDU 2204 Eddy's爱好（容斥原理）

2024-07-14 04:48:44   224人阅读

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

解题报告：输入一个n让你求出[1，n]范围内有多少个数可以表示成形如m^k的样子。

不详细说了，自己一开始也忽略了三个素数的乘积的乘方的情况。

 1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 typedef long long INT; 8 INT prim[70]; 9 10 int dabiao()11 {12     int f = 0;13     for(int i = 2;i < 60;++i)14     {15         int flag = 1;16 17         for(int j = 2;j < i;++j)18         if(i % j == 0)19         {20             flag = 0;21             break;22         }23         if(flag) prim[f++] = i;24     }25     return f;26 }27 28 int calc(INT a,INT b,INT n)29 {30     INT s = 1;31     while(b--)32     {33         if((INT)(n / a) <= s) return 0;34         s *= a;35     }36     return 1;37 }38 int main()39 {40     INT n;41     int num = dabiao();42     while(scanf("%I64d",&n)!=EOF)43     {44         INT tot = 1;45         for(int i = 0;i < num;++i)46         {47             INT temp = (INT)pow((double)n,1.0 / prim[i]);48             if(temp == 1 ) break;   //开方之后不足1的话，则退出49             tot += temp - 1;   //减1是因为每次都会统计到150         }51         for(int i = 0;i < num;++i)52         for(int j = i+1;j < num;++j)53         {54             INT temp = pow((double)n,1.0/(prim[i] * prim[j]));55             if(temp == 1) break;56             tot -= temp - 1;57         }58         for(int i = 0;i < num;++i)59         for(int j = i + 1;j < num;++j)60         for(int k = j + 1;k < num;++k)61         {62             INT temp = pow((double)n,1.0/(prim[i] * prim[j] * prim[k]));63             if(temp == 1) break;64             tot += temp - 1;65         }66         printf("%I64d\n",tot);67     }68     return 0;69 }
View Code

 

HDU 2204 Eddy's爱好（容斥原理）


联系
我们