BZOJ2440 完全平方数

发表于 | 分类于 |
字数统计: 471 字

题目链接

题解

我觉得这题比较简单= =对于这种难以直接求解的问题一般采用二分解决。先二分一个答案$x$，然后看$[1,x]$间有多少个这样的数。
直接算算不出，由于是完全平方数，考虑补集转化，求是完全平方数倍数的个数。有重叠，考虑容斥。答案就是$n-$只有一个质因子的平方数倍数个数$+$有$2$个质因子的$-$有$3$个质因子的…
但是质因子太多，会TLE。
我们知道容斥和莫比乌斯函数有关，所以利用莫比乌斯函数优化。
这样答案就是

二分范围？
观察样例，猜测不会超过。。。
话说这个题 二分有点奇怪 改了一下改成这样才能过？

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
47
48
49
50
51
52
53
54
55
56
57
58
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#define INF 2000000000
using namespace std;
typedef long long ll;
int mu[100005];
int prime[100005],tot=0,n,k;
bool vis[100005]={0};
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}   
int judge(int x){
    int res=0,l=(int)sqrt(x);
    for(int i=1;i*i<=x;i++){
        res+=mu[i]*(x/(i*i));
    }
    return res;
}
void init(){
    mu[1]=1,vis[1]=1;
    for(int i=2;i<=100000;i++){
        if(!vis[i])
            mu[i]=-1,prime[tot++]=i;
        for(int j=0;j<tot;j++){
            ll t=i;t*=(ll)prime[j];
            if(t>100000)break;
            vis[i*prime[j]]=1,mu[i*prime[j]]=-mu[i];
            if(i%prime[j]==0){
                mu[i*prime[j]]=0;
                break;
            }
        }
    }
}
void solve(){
    n=read();
    while(n--){
        k=read();
        int L=1,R=2*k,M;
        while(R-L){
            M=L+(R-L)/2;
            if(judge(M)>=k)R=M;
            else L=M+1;
        } 
        printf("%d\n",L);
    }
}
int main(){
    init();
    solve();
    return 0;
}