Description
- 多测，\(T\) 组数据；
- 每次给出一个整数 \(k\)，求第 \(k\) 小不含平方因子的数（注意：\(1\) 不算平方因子）；
- \(1\le k\le 10^9, T\le 50\)。
Solution
\(n\) 不含平方因子意味着 \(\mu^2(n) = 1\)，而且 \(1\) 也正好满足。
我们设
\[S(n) = \sum_{i = 1}^n \mu^2(i) \]即前 \(n\) 个正整数中有多少个数不含平方因子。
那么考虑到 \(S\) 是单调不减的，直接二分即可，下限显然是 \(k\)，上限可以写程序暴力算 \(k = 10^9\) 的情况，差不多是 \(2k\)，这一步是 \(\log k\) 的。
于是问题转化成快速求 \(S\)。
令
\[f(n) = \mu^2(n) \]首先 \(f\) 肯定是个积性函数，那么直接用杜教筛。
设
\[f * g = h \]如果 \(h = \mathbf{1}\)，那么
\[\begin{aligned} (f * g)(n) & = \sum_{d\mid n} f\left(\dfrac{n}{d}\right) g(d) \\ & = 1 \end{aligned} \]考虑这样一个函数
\[g(n) = [n = m^2, m\in \mathbb{N}^*] \]即 \(n\) 是否为完全平方数。
那么
\[(f * g)(n) = \sum_{d\mid n} f\left(\dfrac{n}{d}\right) g(d) \]只有在 \(d\) 取 \(n\) 的最大平方因子时才有值 \(1\)，即 \((f * g)(n)\) 恒为 \(1\)。
证明：
当 \(d\) 不为完全平方数时，\(g(d) = 0\)；
若 \(d\) 为完全平方数但不为 \(n\) 的最大平方因子，则 \(\dfrac{n}{d}\) 必含大于 \(1\) 的平方因子，\(f\left(\dfrac{n}{d}\right) = 0\)；
当 \(d\) 为 \(n\) 的最大平方因子时，\(\dfrac{n}{d}\) 必不含平方因子，有 \(f\left(\dfrac{n}{d}\right) = g(d) = 1\)。
那么
\[\begin{aligned} g(1) S(n) & = \sum_{i = 1}^n h(i) - \sum_{i = 2}^n g(i) S\left(\left\lfloor\dfrac{n}{i}\right\rfloor \right) \\ & = n - \sum_{i = 2}^n g(i) S\left(\left\lfloor\dfrac{n}{i}\right\rfloor \right) \end{aligned} \]又因为 \(g(1) = 1\)，所以
\[S(n) = n - \sum_{i = 2}^n g(i) S\left(\left\lfloor\dfrac{n}{i}\right\rfloor \right) \]注意 \(g(i)\) 只有在 \(i = m^2\) 时才有值，所以
\[S(n) = n - \sum_{i = 2}^{\left\lfloor\sqrt{n}\right\rfloor} S\left(\left\lfloor\dfrac{n}{i^2}\right\rfloor \right) \]注意到 \(\sqrt{n}\) 并不大，所以别用整除分块了，那玩意儿除法一大堆常数大得要死。
时间复杂度为 \(\Omicron(k^{\frac{2}{3}} + T \log k)\)。
Code
Warning : 注意二分时 \(l + r\) 有可能爆 \(\text{int}\)。
//18 = 9 + 9 = 18.
#include <iostream>
#include <cstdio>
#include <unordered_map>
#include <cmath>
#define Debug(x) cout << #x << "=" << x << endl
typedef long long ll;
using namespace std;
const int MAXN = 1e6 + 5;
const int N = 1e6;
typedef int arr[MAXN];
arr p, mu, sum;
bool vis[MAXN];
void pre()
{
mu[1] = 1;
for (int i = 2; i <= N; i++)
{
if (!vis[i])
{
p[++p[0]] = i;
mu[i] = -1;
}
for (int j = 1; j <= p[0] && i * p[j] <= N; j++)
{
vis[i * p[j]] = true;
if (i % p[j] == 0)
{
mu[i * p[j]] = 0;
break;
}
mu[i * p[j]] = mu[i] * mu[p[j]];
}
}
for (int i = 1; i <= N; i++)
{
sum[i] = sum[i - 1] + mu[i] * mu[i];
}
}
unordered_map<int, int> dp;
int sublinear(int n)
{
if (n <= N)
{
return sum[n];
}
if (dp.count(n))
{
return dp[n];
}
int res = n, upbound = sqrt(n);
for (int i = 2; i <= upbound; i++)
{
res -= sublinear(n / i / i);
}
return dp[n] = res;
}
bool check(int n, int k)
{
if (sublinear(n) >= k)
{
return true;
}
return false;
}
int main()
{
pre();
int t;
scanf("%d", &t);
while (t--)
{
int k;
scanf("%d", &k);
int l = k, r = 2 * k, ans;
while (l <= r)
{
int mid = ((ll)l + r) >> 1;
if (check(mid, k))
{
r = (ans = mid) - 1;
}
else
{
l = mid + 1;
}
}
printf("%d\n", ans);
}
return 0;
}