题解：P11169 「CMOI R1」Bismuth / Linear Sieve

Shadows_of_Twilight · 2024-10-07 13:49:58 · 题解

提示

本片题解用的是题面代码里的变量。

思路

我们可以先特判 n 等于 1 的情况，再讨论其他情况。

首先我们看样例。

• 我们会发现输出的第一个数是 \lceil \frac{n}{2}\rceil。

首先，第一个加入 primes 数组里的是 2，而在后面筛数时只有当前数能整除 2 才能接着用其他的 primes 数组里的数筛，也就是说只有偶数才能用除了 2 的数筛，而偶数乘任何整数还是偶数，且每个数都会筛掉自己的两倍。综上，除 2 以外的偶数都会被筛掉，奇数都不会筛掉，答案就显然了。

第二个输出的数没有那么简单了。虽然 n 始终是第二个数的 3.2 倍左右，但是倍数一直在变。

假设我们现在已经有一个无限长的 primes 数组（数组内填了数）。

你考虑一下什么时候 counter 才会加。显然，如果当前数是 2 的倍数，那么在 j = 1 时 counter 会加；如果当前数是 \operatorname{lcm}(2,3) 的倍数，那么在 j = 2 时 counter 会加……

我们可以预处理出 primes 数组的数和前缀最小公约数（在前缀最小公约数小于 n 的情况下），然后算出 n 以内当前前缀最小公约数的倍数个数（注意要保证这些倍数乘 primes 数组当前的数不超过 n）。把这些倍数个数加起来，就是答案了。

AC CODE

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, cnt, ans;
int p[10000005];

signed main()
{
    cin >> n;
    if (n == 1)
        return cout << 0 << ' '<< 0 << '\n', 0;
    cout << (n + 1) / 2 << ' ';
    int now = 2, ans = 0;
    ans = ans + (n / 2 / 2);
    for (int i = 3;; i += 2)
    {
        if ((__int128)(now / __gcd(now, i) * i > n))
            break;
        now = now / __gcd(now, i) * i;
        ans = ans + (n / i / now);
    }
    cout << ans << '\n';
    return 0;
}