题目链接：BZOJ - 2440
题目分析
首先，通过打表之类的方法可以知道，答案不会超过 2 * k 。
那么我们使用二分，对于一个二分的值 x ，求出 [1, x] 之间的可以送出的数有多少个。
怎么来求呢？我们使用容斥原理。
先求出不能送的数（即含有平方因子的数）有多少个，然后用总数减去就可以了。
那么，就是 含有一个质数平方因子的数(2^2的倍数 + 3^2的倍数 + 5^2的倍数....) - 含有两个质数平方因子的数((2 * 3)^2的倍数 + (2 * 5)^2的倍数 + ...)
这样，奇加偶减，就可以求出含有平方因子的数有多少了。
这样直接容斥来求复杂度很高，我们正好有一种莫比乌斯函数，可以直接算出这个值。
mou(x) = {
1 (x = 1)
(-1)^k (x = p1 * p2 * ... * pk)
0 (x % pi^2 = 0)
}
这样我们可以发现，一个 x 的莫比乌斯函数值和 x^2 在容斥中的系数是相同的。
那么，Ans = sigma(Mou[i] * x / (i*i)) (1 <= i <= Sqrt(x))
莫比乌斯函数可以用线性筛法求出。
代码
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath> using namespace std; typedef long long LL; const int MaxN = 100000 + 5; int T, n, k, Top;
int Mou[MaxN], Prime[MaxN]; bool isPrime[MaxN]; void Prepare()
{
n = 100000;
for (int i = 1; i <= n; ++i) isPrime[i] = true;
isPrime[1] = false; Mou[1] = 1;
Top = 0;
for (int i = 2; i <= n; ++i)
{
if (isPrime[i])
{
Prime[++Top] = i;
Mou[i] = -1;
}
for (int j = 1; j <= Top && i * Prime[j] <= n; ++j)
{
isPrime[i * Prime[j]] = false;
if (i % Prime[j] == 0)
{
Mou[i * Prime[j]] = 0;
break;
}
Mou[i * Prime[j]] = -Mou[i];
}
}
} int Calc(int x)
{
int ret = 0, SqrtX;
SqrtX = (int)sqrt((double)x);
for (int i = 1; i <= SqrtX; ++i)
ret += Mou[i] * x / i / i;
return ret;
} int main()
{
scanf("%d", &T);
Prepare();
for (int Case = 1; Case <= T; ++Case)
{
scanf("%d", &k);
LL l = 1, r = k << 1, mid, Ans;
while (l <= r)
{
mid = (l + r) >> 1;
if (Calc((int)mid) >= k)
{
Ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
printf("%d\n", (int)Ans);
}
return 0;
}