自动搬运

查看原文

来自洛谷，原作者为

	Shadows_of_Twilight Old Id : Xu_dh || 错的不是你，而是这个世界

搬运于2025-08-24 23:04:53，当前版本为作者最后更新于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;
}