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 } View Code

（p.s. Rank.10）

转载于:https://www.cnblogs.com/rausen/p/4114969.html

总结

以上是生活随笔为你收集整理的BZOJ2986 Non-Squarefree Numbers的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。