Description
求第 \(k\) 个不含平方因子的正整数。多组询问。\(k \leq 10^9, T \leq 50\)
Solution
网上的题解几乎都是容斥，这里给一个简单的也挺快的做法。
首先二分答案，然后问题转化成前 \(n\) 个数中有几个不含平方因子的数。
[\(n\) 不含平方因子] \(=\mu^2(n)\)
所以要求的就是 \(\sum\limits_{i=1}^{n}\mu^{2}(i)=\sum\limits_{i=1}^{n}\sum\limits_{d^2|i}\mu(d)=\sum\limits_{d=1}^{\sqrt n}\mu(d)\lfloor\frac{n}{d^2}\rfloor\)
直接筛出 \(\sqrt n\) 以内的所有 \(\mu\) 然后直接 \(\sqrt n\) 算就可以了
非常简单好写，没有啥细节...
复杂度 \(O(T (\sqrt n) (\log n))\) 所以数据范围可以到 1e12 的2333
Code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF = 2 * 1e9;
const int N = 100000;
int T; ll k;
int p[N + 50], flag[N + 50], cnt, mu[N + 50];
inline void prework() {
mu[1] = 1; flag[1] = 1;
for(int i = 2; i <= N; i++) {
if(!flag[i]) {
mu[i] = -1; p[++cnt] = i;
} for(int j = 1; j <= cnt && i * p[j] <= N; j++) {
flag[i * p[j]] = 1;
if(i % p[j] == 0) {
mu[i * p[j]] = 0; break ;
} mu[i * p[j]] = mu[i] * -1;
}
}
}
inline bool check(ll n) {
ll ret = 0;
for(ll d = 1; d * d <= n; d++)
ret += (n / (d * d)) * mu[d];
return ret >= k;
}
int main() {
scanf("%d", &T); prework();
while(T--) {
scanf("%lld", &k);
ll l = 0, r = k * 2, ans;
while(l <= r) {
ll mid = (l + r) / 2;
if(check(mid)) r = mid - 1, ans = mid;
else l = mid + 1;
} printf("%lld\n", ans);
}
return 0;
}