CF1423K Lonely Numbers

继续在CF刷水题

Lonely Numbers

感觉像数学问题，管他那么多先乱推一波：

对于数 $a, b$ 设 $c = \gcd(a, b), a = cd, b = ce$ ，则 $a, b$ 为“友好数”，当且仅当 $c, d, e$ 能够构成三角形

把 $1$ 特判，不妨设 $b > a \ge 2$ ，则 $c + d \ge cd = a$ ，所以……额……好像不对

看样例，发现“孤独数”好像都是质数，再换个方向：

考虑数 $a$ ，设其最小质因数为 $q$ ，考虑 $a + q$ 是离它最近的比它大的“友好数”的条件：

首先 $\gcd(a, a + q) = q$ 且 $\frac{a}{q} + q > \frac{a + q}{q}, \frac{a + q}{q} + q > \frac{a}{q}$ ，现在问题是何时 $\frac{2a + q}{q} > q$
若 $a$ 是合数，则 $a \ge q^2$ ，成立
若 $a$ 是质数，这显然不成立，但我们发现 $a^2$ 是比 $a$ 大的第一个“友好数”

综上，若 $a$ 是合数且最小质因数为 $q$ ，则 $a + q$ 是大于 $a$ 的第一个“友好数”；若 $a$ 是质数，则 $a^2$ 是大于 $a$ 的第一个“友好数”；若 $a = 1$ ，则 $a$ 没有“友好数”

然而 $T, n \le 10^6$ 直接 $O(nT)$ 暴力必炸

还是考虑样例为什么只有质数没有合数，或者说，可否证明小于 $n$ 的合数在 $n$ 以内必有“友好数”

首先 $a + q \le n$ 的情况下明显成立，考虑 $a + q > n$ ，由上面可得，此时 $n$ 以内没有比 $a$ 大的“友好数”，不妨考虑 $a - q$ ：

$\frac{a - q}{q} + q > \frac{a}{q}$ 成立当且仅当 $q^2 > q$ ，即 $q > 1$ ，显然成立
$\frac{a}{q} + q > \frac{a - q}{q}$ ，显然成立
$\frac{2a - q}{q} > q$ ，因为 $a \ge q^2$ 所以成立

于是，对与合数， $a - q$ 是小于 $a$ 的第一个“友好数”

那么，现在，我们要证明对于 $a \le n < a + q$ ，必有 $1 \le a - q$ ，因为 $a$ 是合数，这显然成立

于是，我们得到 $n$ 以内的“孤独数”判定方法：对应合数，它一定不是“孤独数”；对于质数，只要它的平方小于 $n$ 它就不是“孤独数”，否则就是“孤独数”

那么就很显然了，预处理出质数个数的前缀和，答案就是 sum[n] - sum[sqrt(n)] + 1 （ $1$ 本身单独算）

#include <bits/stdc++.h>
#define STC static
#define LL long long
using namespace std;
const int N = 1e6 + 5;
int prime[N], cnt = 0;
int v[N], sum[N];
void prev()
{
    for (int i = 2; i < N; ++i)
    {
        if (!v[i])
            prime[++cnt] = v[i] = i;
        for (int j = 1; j <= cnt && prime[j] * i < N; ++j)
        {
            if (prime[j] > v[i])
                break;
            v[prime[j] * i] = prime[j];
        }
    }
    for (int i = 1; i < N; ++i)
        sum[i] = sum[i - 1] + (v[i] == i);
}
int main()
{
    prev();
    int T, n;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        printf("%d\n", sum[n] - sum[(int)sqrt(n)] + 1);
    }
    return 0;
}