HDU 2204 Eddy's爱好 容斥

本文主要是介绍HDU 2204 Eddy's爱好 容斥，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

输入n，求出1~n中，有多少个值可以表示为M^K（K>1）。

思路：

容斥。这题算是我的容斥第一题吧。现在回头看容斥原理，就是奇数个集合就加，偶数个集合就减（说得貌似顶简单，在做题过程中找该容斥什么也蛮累的= =）。

首先看这个，对于2^4和4^2，如果直接计算个数，这样会导致重复。因此指数应该强制为质数（素数），则可以避免这个问题（根据算术基本定理，一个大于1的值总能表示为素数的积，因此这样限制之后，是不会遗漏掉某个数值的。）

即使指数为质数，也同样会存在重复，例如T^3 = P ^ 5（T = t^5，P = t^3）。这里就用到了容斥原理来排除重复计数。

1.在小于等于n中，能表示为5次方的个数为。

2.因为2^60>1e18，因此我们只要筛选出小于60的素数即可。

容斥过程：

1.加上指数为2，3，5，7，11……的个数。

2.减去指数2*3，2*5，2*7，……，3*5，3*7，……，……的个数。

3.因为2*3*5*7>60，因此三个集合就只有（2，3，5）。加上指数为2*3*5的个数后即为最终结果。

这题不卡pow，但还是要加上1e-9来解决精度问题。

code：

#include <cstring>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <cstdlib>
using namespace std;
typedef long long ll;
#define eps 1e-8const int MAXN = 65;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
int isprime[MAXN], prime[MAXN];
int cot;
int getPrime(int N)
{int sx = sqrt(N);for(int i = 2; i <= sx; i++){if(isprime[i] == 0){for(int j = i*i; j <= N; j += i)isprime[j]++;}}cot = 0;for(int i = 2;i <= N; i++)if(isprime[i] == 0)prime[cot++] = i;//, cout<<i<<" ";//puts("");
}
int main()
{ll n;getPrime(60);while(scanf("%I64d", &n) != EOF){//onell res = 1, tmp;for(int i = 0; i < cot; i++){tmp = (ll)(pow((double)n, 1.0/prime[i])+eps);//tmp = test(n, prime[i], tmp);//cout<<tmp<<endl;if(tmp == 1)    break;res += (tmp-1);}//cout<<res<<endl;//twofor(int i = 0;i < cot; i++)for(int j = i+1;j < cot; j++){tmp = (ll)(pow((double)n, 1.0/(prime[i]*prime[j]))+eps);//if(test(tmp, prime[i]*prime[j])if(tmp == 1)    break;res -= (tmp-1);}//cout<<res<<endl;//threefor(int i = 0; i < cot; i++)for(int j = i+1;j < cot; j++)for(int z = j+1;z < cot; z++){tmp = (ll)(pow((double)n, 1.0/(prime[i]*prime[j]*prime[z])+eps));if(tmp == 1)    break;res += (tmp-1);}printf("%I64d\n", res);}return 0;
}

本题还有另一种解法，我是做了hdu 3208后想到套用的。

思路可以看这里http://blog.csdn.net/u011580493/article/details/43172335

code：

#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;typedef long long LL;
const double eps = 1e-9;
LL a[65];int main()
{LL n;while(scanf("%I64d", &n) != EOF){memset(a, 0, sizeof(a));int cnt = 1;for(int i = 2;i <= 60; i++){a[i] = (LL)(pow((double)n, 1.0/i) + eps);a[i]--;if(a[i] == 0) break;cnt = i;}for(int i = cnt;i > 1; i--)for(int j = 1;j < i; j++)if(i%j == 0) a[j] -= a[i];LL res = 1;for(int i = 2;i <= cnt; i++)res += a[i];printf("%I64d\n", res);}return 0;
}

这篇关于HDU 2204 Eddy's爱好 容斥的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---