首页 > 代码库 > 【BZOJ】2440: [中山市选2011]完全平方数(莫比乌斯+容斥原理+二分)
【BZOJ】2440: [中山市选2011]完全平方数(莫比乌斯+容斥原理+二分)
http://www.lydsy.com/JudgeOnline/problem.php?id=2440
我觉得网上很多题解都没说清楚。。。(还是我太弱了?
首先我们可以将问题转换为判定性问题,即给出一个数x,有多少个小于x等于的数是不能分解的,即不是完全平方数(不包括1)。
而每个数都可以写成质数积,那么显然只要质数的平方的倍数就可以代替所有数的平方的倍数。
考虑质数个数,假设质数集$P$,那么根据容斥原理,在x范围内的正整数能分解的个数有:
$$(A_{p_1} + A_{p_2} + \cdots + A_{p_k}) - (A_{p_1, p_2} + A_{p_1, p_3} + \cdots + A_{p_{k-1}, p_k}) + \cdots + (-1)^{k+1} A_{p_1, p_2, \cdots , p_k}$$
其中$A(S)$表示S乘积的平方倍数能分解的个数,而且指数均为1。然后用总数减去这个数就是答案。
而我们考虑莫比乌斯函数的定义,发现当$\mu (x)=(-1)^k$的定义恰好是指数均为1的定义!而符号又决定了容斥的符号!哈哈!
所以我们预处理mu后,因为根据每个数的最大平方因子为$\sqrt(x)$,那么我们只要枚举$\sqrt(x)$个数,然后用莫比乌斯来搞就行了!
#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define error(x) (!(x)?puts("error"):0)inline const ll getint() { ll r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }#define rdm(x, i) for(int i=ihead[x]; i; i=e[i].next)const int N=1e5+10;int mu[N], p[N], np[N], cnt;void init() { mu[1]=1; for2(i, 2, N) { if(!np[i]) p[++cnt]=i, mu[i]=-1; for1(j, 1, cnt) { int t=p[j]*i; if(t>=N) break; np[t]=1; if(i%p[j]==0) { mu[t]=0; break; } mu[t]=-mu[i]; } }}ll cal(ll x) { int s=sqrt(x+0.5); ll ret=0; for1(i, 1, s) ret+=mu[i]*(x/(1ll*i*i)); return ret;}int main() { init(); int T=getint(); while(T--) { ll k=getint(), l=1, r=k<<1; while(l<=r) { ll mid=(l+r)>>1; if(cal(mid)>=k) r=mid-1; else l=mid+1; } printf("%lld\n", r+1); } return 0;}
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
Source
【BZOJ】2440: [中山市选2011]完全平方数(莫比乌斯+容斥原理+二分)