本文主要是介绍BZOJ 2440 完全平方数 (容斥＋莫比乌斯反演＋二分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
2440: [中山市选2011]完全平方数
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1673 Solved: 799
[ Submit][ Status][ Discuss]
Description
小 X 自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些
数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而
这丝毫不影响他对其他数的热爱。
这天是小X的生日，小 W 想送一个数给他作为生日礼物。当然他不能送一
个小X讨厌的数。他列出了所有小X不讨厌的数，然后选取了第 K个数送给了
小X。小X很开心地收下了。
然而现在小 W 却记不起送给小X的是哪个数了。你能帮他一下吗？
Input
包含多组测试数据。文件第一行有一个整数 T，表示测试
数据的组数。
第2 至第T+1 行每行有一个整数Ki，描述一组数据，含义如题目中所描述。
Output
含T 行，分别对每组数据作出回答。第 i 行输出相应的
第Ki 个不是完全平方数的正整数倍的数。
Sample Input
1
13
100
1234567
Sample Output
19
163
2030745
HINT
对于 100%的数据有 1 ≤ Ki ≤ 10^9, T ≤ 50
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2440
题目分析：题目要求第k个无平方因子数，我们显然不可能把答案都求出来再查询，这个数据范围首先想到的是二分，对于第1-n的无平方因子数我们可以用容斥定理得到，拿总的个数减去4的倍数(-n/4个)，减去9的倍数(-n/9个)，但是36既是4的倍数又是9的倍数，被减了两次，要加回来(+n/36)，这样容斥就出来了，前面的符号正好和数字开根号后对应的莫比乌斯函数相同，这样问题就简单了，还有一点要说明的是二分的上界开多大，这个也影响着莫比乌斯函数要开多大，我们不妨假设第k个无平方因子数不会超过2k，具体证明我也不会，但是最小的平方因子是4，也就是说每4个数里必然有一个是平方因子数，同时因为平方因子越往后越大，可以yy出平均每四个数有不超过两个平方因子数这个结论，所以第k个无平方因子数不会超过2k，(其实打表也可验证)，所以二分上界取2k+1即可，莫比乌斯函数开sqrt(2e9)差不多5e4的样子
1000ms过
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
int const MAX = 5e4;
ll const INF = 2e9;
int mob[MAX], p[MAX];
bool prime[MAX];void Mobius()
{int pnum = 0;memset(prime, true, sizeof(prime));mob[1] = 1;for(int i = 2; i < MAX; i++){if(prime[i]){p[pnum ++] = i;mob[i] = -1;}for(int j = 0; j < pnum && i * p[j] < MAX; j++){prime[i * p[j]] = false;if(i % p[j] == 0){mob[i * p[j]] = 0;break;}mob[i * p[j]] = -mob[i];}}
}ll cal(int mid)
{ ll pos = 0;for(int i = 1; i * i <= mid; i++)pos += (ll) mob[i] * (mid / (i * i));return pos;
}int main()
{Mobius();int T;scanf("%d", &T);while(T--){ll k;scanf("%lld", &k);ll l = 1, r = 2 * k + 1;while(l <= r){ll mid = (l + r) >> 1;if(cal(mid) < k)l = mid + 1;elser = mid - 1;}printf("%lld\n", l);}
}
这篇关于BZOJ 2440 完全平方数 (容斥＋莫比乌斯反演＋二分)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
