Description
求第k个无平方因子数。无平方因子数指分解之后所有质因数的次数都为1的数。
Solution
我们可以进行二分操作，查找区间[1,x]里有几个无平方因子数，逐渐缩小范围依次求解。
然而怎么计算区间[1,x]内无平方因子数的个数Q呢？
根据容斥原理
Q=x−x内有一个平方因子的数+x内有两个平方因子的数−x内有三个平方因子的数...=x−x内(4的倍数个数+9的倍数的个数+25的倍数的个数)+x内(36(2∗3∗2∗3)的倍数+100(2∗5∗2∗5)的倍数)...=i=2∑x±i2n
现在的问题是，对于某个n/(i*i),到底是取正还是取负呢？
我们发现，对于有奇数个质数平方的因子数取正，有偶数个质数平方的因子数取正，仔细一看，这不正是i的莫比乌斯函数值吗？于是可求出$$Q=\sum_{i=2}^{\sqrt{x}}\mu(i)\frac{n}{i^2}$$
然后就可以愉快的AC辣！
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include<cmath>
#include<cstdio>
typedef long long ll;
const ll maxx=(ll)1<<32;
const int maxlim=1<<16;
bool form[maxlim];
int mu[maxlim]={0,1},prime[maxlim],cnt;
void MakeMuList(){
for(int i=2;i<maxlim;i++){
if(!form[i]) prime[cnt++]=i,mu[i]=-1;
for(int j=0,t=prime[j]*i;t<maxlim;j++,t=prime[j]*i){
form[t]=true;
if(!(i%prime[j])){ mu[t]=0; break; }
mu[t]=-mu[i];
}
}
}
ll query(ll x){
int lim=sqrt(x);
ll ans=x;
for(int i=2;i<=lim;i++) ans+=mu[i]*(x/(i*i));
return ans;
}
void find(int k){
if(k==1){ printf("1\n"); return; }
int num=0;
ll l=1,r=1644934081,x=0;
while(l<=r){
ll mid=(l+r)>>1;
num=query(mid);
if(num>=k) r=mid-1,x=mid;
else l=mid+1;
}
printf("%lld\n",x);
}
int main(){
MakeMuList();
int kase; scanf("%d",&kase);
while(kase--){
int k; scanf("%d",&k);
find(k);
}
return 0;
}
|
