首页 > 代码库 > BZOJ 2440: [中山市选2011]完全平方数 二分答案 + 容斥原理 + 莫比乌斯反演
BZOJ 2440: [中山市选2011]完全平方数 二分答案 + 容斥原理 + 莫比乌斯反演
http://www.lydsy.com/JudgeOnline/problem.php?id=2440
第一道莫比乌斯反演的题目。
二分答案 + 容斥那里还是挺好想的。
二分一个答案val,需要[1, val]之间存在的合法数字个数 >= k即可。
怎么判断呢?可以容斥,开始的时候有ans = val个,但是这里明显有些数字不符合。
ans -= ([1...val]中有多少个2^2倍 + [1...val]中有多少个3^2倍 + [1...val]中有多少个5^2倍) ......
但是减重复了,比如减去了2^2倍的,减去了3^2倍的,36就被减去了两次。
这个时候就要加回来。所以就要求出sqrt(val)之间有多少个素数,然后暴力dfs每一个素数选不选,一共选了多少个。
但是这样铁定超时啊,复杂度2^k(k为小于等于sqrt(val)中有多少个素数)
然后学了个新姿势Mobius反演。
具体东西如下:
那么换一种思路来快速求解[1, val]中合法数字的个数。
考虑暴力枚举 <= sqrt(val)中所有数字的平方倍。
也就是2^2、3^2、4^2......
那么每次就会有:
4、8、12、16、20、24、28、32、36
9、18、27、36、45、54、63、....
16、32、48、54、60、.....
....
36、72、108.....
每次都减去所有的这些倍数,显然不行,因为有些减多了。
第一、比如被2^2筛走的,4^2就无需再晒,注意到mu[4] = 0刚好满足。
第二、被2^2筛走了一次,又被3^2筛走了一次的,比如数字36,需要加回来,注意到mu[6] = 1也刚好满足。
所以公式是,可以暴力枚举 <= sqrt(val)中所有数字的平方倍。
ans += mu[i] * val / (i * i)
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> const int maxn = 1e6 + 20; int prime[maxn];//这个记得用int,他保存的是质数,可以不用开maxn那么大 bool check[maxn]; int total; int mu[maxn]; void initprime() { mu[1] = 1; //固定的 for (int i = 2; i <= maxn - 20; i++) { if (!check[i]) { //是质数了 prime[++total] = i; //只能这样记录,因为后面要用 mu[i] = -1; //质因数分解个数为奇数 } for (int j = 1; j <= total; j++) { //质数或者合数都进行的 if (i * prime[j] > maxn - 20) break; check[i * prime[j]] = 1; if (i % prime[j] == 0) { mu[prime[j] * i] = 0; break; } mu[prime[j] * i] = -mu[i]; //关键,使得它只被最小的质数筛去。例如i等于6的时候。 //当时的质数只有2,3,5。6和2结合筛去了12,就break了 //18留下等9的时候,9*2=18筛去 } } return ; } int k; bool isok(LL val) { LL ans = val; for (LL i = 2; i * i <= val; ++i) { ans += mu[i] * (val / (i * i)); } return ans >= k; } void work() { scanf("%d", &k); LL be = 1, en = 2e9; while (be <= en) { LL mid = (be + en) >> 1; // cout << mid << endl; if (isok(mid)) { en = mid - 1; } else be = mid + 1; } printf("%d\n", be); } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif initprime(); // for (int i = 1; i <= 20; ++i) { // cout << mu[i] << ","; // } int t; scanf("%d", &t); while (t--) work(); return 0; }
BZOJ 2440: [中山市选2011]完全平方数 二分答案 + 容斥原理 + 莫比乌斯反演