本文主要是介绍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爱好 容斥的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!