首页 > 代码库 > BZOJ2986 Non-Squarefree Numbers
BZOJ2986 Non-Squarefree Numbers
神马的容斥原理实在是太神啦！
就是先二分一个数mid，看看有几个满足要求的数比他小。
查看的方法就是容斥原理。。。
res = ((2 ^ 2)倍数个数 - ((2 ^ 2) * (3 ^ 2)倍数个数 + (2 ^ 2) * (5 ^ 2)倍数个数 + ...) + (((2 ^ 2) * (3 ^ 2) * (5 ^ 2)倍数个数 + .....)) + ((3 ^ 2)倍数个数...)
我去。。。这复杂度真的能过= =
1 /************************************************************** 2 Problem: 2986 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:1512 ms 7 Memory:5688 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 12 using namespace std;13 typedef long long ll;14 const int N = 1000005;15 16 int p[N], cnt;17 bool F[N];18 ll n;19 20 ll find(int f, int i, ll mid) {21 ll res = 0, sqr;22 for (; i <= cnt && (sqr = (ll) p[i] * p[i]) <= mid; ++i)23 res += (ll) mid / sqr * f + find(-f, i + 1, mid / sqr);24 return res;25 }26 27 void pre_work(int M) {28 int i, j;29 for (i = 2; i <= M; ++i) {30 if (!F[i])31 p[++cnt] = i;32 for (j = 1; i * p[j] <= M && j <= cnt; ++j) {33 F[i * p[j]] = 1;34 if (i % p[j] == 0) break;35 }36 }37 }38 39 int main() {40 pre_work(N);41 scanf("%lld", &n);42 ll l = 1, r = (ll) 1e11, mid;43 while (l < r) {44 mid = (ll) l + r >> 1;45 if (find(1, 1, mid) < n) l = mid + 1;46 else r = mid;47 }48 printf("%lld\n", l);49 return 0;50 }
（p.s. Rank.10）
BZOJ2986 Non-Squarefree Numbers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。