BZOJ 2440: [中山市选2011]完全平方数

题目地址

描述

小 X 自幼就很喜欢数。但奇怪的是,他十分讨厌完全平方数。他觉得这些
数看起来很令人难受。由此,他也讨厌所有是完全平方数的正整数倍的数。然而
这丝毫不影响他对其他数的热爱。
这天是小X的生日,小 W 想送一个数给他作为生日礼物。当然他不能送一
个小X讨厌的数。他列出了所有小X不讨厌的数,然后选取了第$K$个数送给了
小X。小X很开心地收下了。
然而现在小 W 却记不起送给小X的是哪个数了。你能帮他一下吗?
$T$为数据组数,对于100%的数据有 $1 \leq K_{i} \leq 10^{9},T \leq 50$。

分析

看到这个的时候很容易想到二分$n$,计算区间$[1, n]$有多少个无平方因子的数。

如果我们要计算区间$[1, n]$有无平方因子的数的个数就要用到容斥原理。

很明显我们的答案可表示为

然后我们会发现每一个数前面的符号其实对应的就是它的莫比乌斯函数的值。

综上所述,我们可以整理一个区间$[1, n]$答案为:

代码

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
59
60
61
62
63
64
65
66
67
//2017/06/14 11:31:39
//Copyright (c) 2017年 ZJYelizavtea. All rights reserved.
//BZOJ 2440: [中山市选2011]完全平方数
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int readIn(){
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX = 1000000 + 3;
const int INF = 0x3f3f3f3f;
int testCase;
int K;
int prime[MAX + 3], mu[MAX + 3];
bool isNotPrime[MAX + 3];

inline void seive(){
memset(isNotPrime, false, sizeof isNotPrime);
int cnt = 0;
isNotPrime[1] = true, mu[1] = 1;
for(int i = 2; i <= MAX; ++i){
if(!isNotPrime[i]){
prime[++cnt] = i;
mu[i] = -1;
}
for(int j = 1; j <= cnt && i * prime[j] <= MAX; ++j){
isNotPrime[i * prime[j]] = true;
if(i % prime[j] == 0){
mu[i * prime[j]] = 0;
break;
}
else mu[i * prime[j]] = -mu[i];
}
}
//for(int i = 1; i <= 12; ++i) printf("%d ", mu[i]); printf("\n");
}

bool check(int n){
int ans = 0;
for(int i = 1; i * i <= n; ++i){
ans += mu[i] * n / (i * i);
}
if(ans < K) return true;
else return false;
}

int main()
{
seive();
testCase = readIn();
while(testCase--){
K = readIn();
ll l = 0, r = K * 2;
while(r - l > 1){
ll mid = (l + r) >> 1;
if(check(mid)) l = mid;
else r = mid;
}
printf("%lld\n", l + 1);
}
return 0;
}
Partager