BZOJ2440【中山市选2011】完全平方数 <二分+莫比乌斯容斥>

Posted on Symbols count in article: 802 Reading time ≈ 3 mins.

Problem

【中山市选2011】完全平方数

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  128  MB\mathrm{Memory\;Limit:\;128\;MB}

Description

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

Input

包含多组测试数据。文件第一行有一个整数TT，表示测试数据的组数。
第22至第T+1T+1行每行有一个整数KiK_i，描述一组数据，含义如题目中所描述。

Output

含TT行，分别对每组数据作出回答。第ii行输出相应的第KiK_i个不是完全平方数的正整数倍的数。

Sample Input

1
2
3
4
5
4
1
13
100
1234567

Sample Output

1
2
3
4
1
19
163
2030745

HINT

对于100%100\%的数据有1≤Ki≤109,  T≤501\le K_i\le10^9,\;T\le50

标签：二分答案 莫比乌斯容斥

Solution

QAQ\mathrm{QAQ}没做起水题…

似乎答案不超过2×K2\times K？不会证。

二分答案，对于当前尝试的答案nn，统计nn以下有多少个符合条件的数。
符合条件的数的个数=n−完全平方数的倍数的个数符合条件的数的个数=n-完全平方数的倍数的个数
容易发现为了避免算重复，可以约数容斥来算。另外，如果完全平方数的底数有平方因子，一定不会产生贡献。
设所有质数的集合为S1S_1，所有由两个不同质数相乘而得数的集合为S2S_2，…，由qq个不同质数相乘而得的数的集合为SqS_q，那么符合条件的数的个数为：

cnt=∑i2∈S1⌊ni2⌋−∑i2∈S2⌊ni22⌋+∑i3∈S3⌊ni32⌋−⋯cnt=\sum_{i_2\in S_1}\lfloor\frac{n}{i^2}\rfloor-\sum_{i_2\in S_2}\lfloor\frac{n}{i_2^2}\rfloor+\sum_{i_3\in S_3}\lfloor\frac{n}{i_3^2}\rfloor-\cdots\\

发现上面的式子可以用莫比乌斯函数简化，即

cnt=∑i=1nμ(i)⋅⌊ni2⌋cnt=\sum_{i=1}^{\sqrt{n}}\mu(i)\cdot\lfloor\frac{n}{i^2}\rfloor

这样每次用O(n)O(\sqrt{n})时间checkcheck，总复杂度为O(Klog⁡K)O(\sqrt{K}\log{K})。

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
#include <bits/stdc++.h>
#define MAX_N 50000
#define mid (l+((r-l)>>1))
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
bool NotPri[MAX_N+5];
int pri[MAX_N+5], mu[MAX_N+5], cnt;
void init() {
    mu[1] = 1;
    for (int i = 2; i <= MAX_N; i++) {
        if (!NotPri[i]) pri[cnt++] = i, mu[i] = -1;
        for (int j = 0; j < cnt; j++) {
            if (i*pri[j] > MAX_N) break;
            NotPri[i*pri[j]] = true;
            if (i%pri[j]) mu[i*pri[j]] = -mu[i];
            else {mu[i*pri[j]] = 0; break;}
        }
    }
}
bool chk(int n, int k) {
    int rk = 0;
    for (int i = (int)sqrt(n); i; i--)
        rk += mu[i]*(n/i/i);
    return rk >= k;
}
void sol(int k) {
    int l = 1, r = 2*k, ans = -1;
    while (l <= r)
        if (!chk(mid, k)) l = mid+1;
        else ans = mid, r = mid-1;
    printf("%d\n", ans);
}
int main() {
    int T, k;	read(T), init();
    while (T--) read(k), sol(k);
    return 0;
}