BZOJ-2440-完全平方数-中山市选2011-容斥原理-莫比乌斯函数-二分查找

描述

小 X 自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。这天是小X的生日，小 W 想送一个数给他作为生日礼物。当然他不能送一个小X讨厌的数。他列出了所有小X不讨厌的数，然后选取了第 K个数送给了小X。小X很开心地收下了。然而现在小 W 却记不起送给小X的是哪个数了。你能帮他一下吗？

分析

• 本来准备做数表, 抱着学习的心态看了看莫比乌斯反演, 看到莫比乌斯函数之后不想再往下看了就来做了这个题.
• 这是一种基于二分的方法. 用到了容斥原理和莫比乌斯函数
• 根据容斥原理可知 对于sqrt(x)以内所有的质数 有
•   x以内的无平方因子数
• = 0个质数乘积的平方的倍数的数的数量(1的倍数) = x
• - 每个质数的平方的倍数的数的数量(9的倍数,25的倍数,...)
• +每2个质数乘积的平方的倍数的数的数量(36的倍数,100的倍数,...)
• ...
• 容易发现每个乘积a前面的符号恰好是mu[a]. x以内i^2的倍数有X/(i^2)向下取整. 所以二分, 计算x以内的无平方因子数. 直到找到第k个无平方因子数.

代码

#include #include using namespace std; typedef long long int lli;const int maxn = 100000 + 10; int c, prime[maxn], mu[maxn]; bool vis[maxn];void get_mu() {mu[1] = 1;for(int i = 2; i < maxn; i++) {if(!vis[i]) prime[++c] = i, mu[i] = -1;for(int j = 1; prime[j]*i < maxn; j++) {int k = prime[j] * i;vis[k] = 1;if(i % prime[j] == 0) { mu[k] = 0; break; }mu[k] = -mu[i];}} }lli calc(int x) {lli ret = 0;int m = (int)(sqrt(x) + 0.5);for(int i = 1; i <= m; i++) ret += (lli)mu[i] * x/(i*i);return ret; }lli twiDivide(lli n) {lli l = n, r = n << 1;while(l <= r) {lli m = (l+r) >> 1;if(calc(m) >= n) r = m-1; else l = m+1;}return r+1; }int main() {get_mu();int T;scanf("%d", &T);while(T--) {lli n;scanf("%lld", &n);printf("%lld\n", twiDivide(n));}return 0; }

与50位技术专家面对面20年技术见证，附赠技术全景图

总结

以上是生活随笔为你收集整理的BZOJ-2440-完全平方数-中山市选2011-容斥原理-莫比乌斯函数-二分查找的全部内容，希望文章能够帮你解决所遇到的问题。

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