BZOJ2986:NonSquarefreeNumbers[容斥原理二分]

题意求第\(n \le 10^{10}\)个不是无平方因子数

二分答案 容斥一下0个质数的平方因子-1个..... 枚举\(\sqrt{mid}\)的平方因子乘上莫比乌斯函数最后求出无平方因子数的个数取补集

#include #include #include #include #include using namespace std;const int N3e55;typedef long long ll;inline ll read(){char cgetchar();ll x0,f1;while(c9){if(c-)f-1;cgetchar();}while(c>09){xx*10c-0;cgetchar();}return x*f;}ll k;int notp[N], p[N], mu[N];void sieve(int n) {mu[1] 1;for(int i2; i1;if(check(mid)) ansmid, rmid-1;else lmid1;}printf("%lld\n",ans);}