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

Hopeful_Hunter · 2024-10-06 00:26:49 · 题解

首先观察样例发现第一个样例一定是 \lceil \frac{n}{2} \rceil。

手推一下加入数字的过程：

当处理到数字二时，此时 cntp = 1, counter = 1，并将 isnotprime_{4} 赋值为 1。

当处理到数字三时，此时 cntp = 2, counter = 2，并将 isnotprime_{6} 赋值为 1。

......

首先大于所有大于 1 的奇数而言更新其他数字是否被筛到时，则必然枚举到 2 就停止了。

接着对于所有大于 0 的偶数而言更新其他数字是否被筛到时，由于本身是偶数，所以其筛出的数也必然是偶数。

由于两种筛法都没有办法筛出奇数，而 n 以内大于 1 的奇数有 \lceil \frac{n - 2}{2} \rceil 个，接着 2 一开始没有被筛到，所以 cntp 一定为 \lceil \frac{n - 2}{2} \rceil + 1 = \lceil \frac{n}{2} \rceil。

接着考虑计算 counter 的值，对于每个未被筛到的元素单独考虑贡献，假设 x 为筛倍数时筛到当前考虑的元素中某个 i，当前考虑元素为 y，l 为未被筛到的元素中小于等于 y 的 \operatorname{lcm}。

首先必然有 x \times y \le n，那么现在 x 的范围在 [1, \lfloor \frac{n}{2} \rfloor] 之内，那么 x 整除 l，由于 l 增长速度较快，所以需要考虑的元素数量较少，那么只需要考虑这些 l \le n 中未被筛到的元素。

注意：

代码如下：

#include<bits/stdc++.h>

using namespace std;

long long n;

long long gcd(long long a, long long b){
  return !b ? a : gcd(b, a % b);
}

long long lcm(long long a, long long b){
  return a / gcd(a, b) * b;
}

int main(){
  cin >> n;
  if(n == 1){
    cout << 0 << ' ' << 0;
    return 0;
  }
  cout << (n + 1) / 2 << ' ';
  long long ans = (n / 2) / 2;
  long long l = 2;
  for(long long i = 2; 2 * i - 1 <= n; i++){
    long long nw = 2 * i - 1;
    l = lcm(l, nw);
    if(l > n) break;
    ans += (n / nw) / l;
  }
  cout << ans;
  return 0;
}