HDU 2204 / 容斥原理
大意:求在中可以表示为形式的数的个数()
这道题不像是有的解法,但是哪怕是的算法也会超时,因此直觉上我们应该寻找的是的算法。
首先,因为的情形是trivial的,所以考虑此时,这也是的一个上界。
接下来我们发现:如果一个数可以表示为的形式,也一定可以表示为的形式,类似地,如果是合数的话,那么一定可以表示为和 。
令表示可以表示为形式的数的个数,那么题目显然要我们求的是:
接下来就用容斥原理很快就能解决这道题了,代码非常的简洁,注意精度:#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
const double EPS = 1e-8;
const int p[] = { 0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59 };
ll n;
ll calc(ll d, ll a) {
if (a > 60) return 0;
if (d == 0)
return a == 1 ? 0 : (ll)(pow(n, 1.0 / a) + EPS) - 1;
return calc(d - 1, a) - calc(d - 1, a * p[d]);
}
int main() {
while (scanf("%lld", &n) != EOF)
printf("%lld\n", -calc(17, 1) + 1);
return 0;
}