Moe's CF Life

Appearance

D. Soldier and Number Game - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 304 (Div. 2) 标签: constructive algorithms, dp, math, number theory 难度: *1700

喵喵，我们来分析一下题目吧！ ​

主人你好呀~！这道题是一个非常有趣的数字游戏呢，喵~

游戏是这样的：

  1. 第一个士兵选一个正整数 n，这个 n 很特别，是 a! / b! 的形式（a! 表示 a 的阶乘，就是从 1 乘到 a 的所有整数）。
  2. 第二个士兵开始玩游戏，每一轮他可以选一个大于 1 的整数 x，只要 n 能被 x 整除，他就可以把 n 变成 n / x。
  3. 游戏一直进行到 n 变成 1 为止。第二个士兵的目标是进行尽可能多的轮次。

我们的任务就是，对于给定的 a 和 b，计算出第二个士兵最多能玩多少轮，也就是他的最高分是多少，的说！

输入会给我们很多组 a 和 b，我们需要对每一组都快速给出答案，喵~

解题思路大揭秘喵~ ​

要让轮次最多，我们应该怎么做呢？(ฅ'ω'ฅ)

思考一下，每次我们都用 n 除以一个数 x。如果 x 是一个合数，比如 x = y * z，那么用 n 除以 x 这一轮，其实等价于先用 n 除以 y，再用结果除以 z 这两轮。所以，为了让轮次最多，我们每次都应该选择一个质数来除 n！

这样一来，问题就转化成：数字 n = a! / b! 的质因数分解中，所有质数的指数之和是多少？

举个例子，如果 n = 12，它的质因数分解是 2^2 * 3^1。我们可以进行 12 -> 6 -> 3 -> 1（除以2，再除以2，再除以3），总共 3 轮。这个 3 正好就是指数之和 2 + 1。在数论中，这个“质因数分解中所有质数的指数之和”被称为 Omega 函数，记作 Ω(n)。

所以，我们的目标就是计算 Ω(a! / b!)。

根据 a! / b! 的定义，我们知道 a! / b! = (b + 1) * (b + 2) * ... * a。 Omega 函数有一个非常棒的性质，那就是 Ω(x * y) = Ω(x) + Ω(y)。 所以，我们可以把原问题拆解开来： Ω(a! / b!) = Ω((b + 1) * (b + 2) * ... * a)= Ω(b + 1) + Ω(b + 2) + ... + Ω(a)

哇！问题变成了计算从 b+1 到 a 这一系列数字的 Ω 函数值的总和！ Score = Σ_{i=b+1 to a} Ω(i)

但是，题目给的数据范围很大，a 和 b 可以到 5,000,000，查询次数 t 也很多。如果我们每次查询都循环一次从 b+1 到 a 来计算，肯定会超时的说！(｡>﹏<｡)

这时候就要祭出我们的优化大法——预处理和前缀和！

我们可以先预处理出从 1 到 5,000,000 每个数字 i 的 Ω(i) 值。然后，再计算一个前缀和数组 prefix_sum[k] = Σ_{i=1 to k} Ω(i)。 这样，对于每个查询 (a, b)，Σ_{i=b+1 to a} Ω(i) 就可以用 prefix_sum[a] - prefix_sum[b] 在 O(1) 的时间内算出来啦！

那么，怎么快速预处理出所有 Ω(i) 呢？ 我们可以用一个类似筛法的思路：

  1. 筛出最小质因子 (Smallest Prime Factor, spf)：我们先用一个类似埃氏筛的方法，预处理出一个 spf 数组。spf[i] 存储数字 i 的最小质因子。

    • 初始化 spf[i] = i。
    • 从 2 开始遍历，如果 i 是一个质数（即 spf[i] == i），就把它所有的倍数 j 的 spf[j] 更新为 i（如果 spf[j] 还没被更新过的话）。

  2. 动态规划计算 Ω(i)：有了 spf 数组，计算 Ω(i) 就变得非常简单了！我们可以发现一个递推关系： Ω(i) = Ω(i / spf[i]) + 1 这是因为 i 可以看作是它的最小质因子 spf[i] 乘上 i / spf[i]。根据 Ω 函数的性质，Ω(i) 就是 Ω(i / spf[i]) 的值再加上 spf[i] 这一个质因子的贡献（也就是 +1）。 我们可以从 2 开始，一路计算到 MAXN，这样每个 Ω(i) 都能在 O(1) 时间内由更小的值推导出来。

总结一下我们的完整计划喵~：

  1. 预处理阶段 (只做一次):
    • 用筛法计算出 1 到 5,000,000 所有数字的最小质因子 spf[i]。
    • 用动态规划 Ω(i) = Ω(i / spf[i]) + 1 计算出所有 Ω(i) 的值。
    • 计算 Ω(i) 的前缀和数组 prefix_sum_omega。
  2. 查询阶段 (对于 t 次查询):
    • 读入 a 和 b。
    • 答案就是 prefix_sum_omega[a] - prefix_sum_omega[b]。

这样一来，我们就可以光速完成所有查询啦！是不是很巧妙呢，喵~ (´,,•ω•,,)♡

AC代码大放送！ ​

cpp
#include <iostream>

// 加速C++的I/O，让程序跑得飞快喵~
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

// 根据题目约束，a的最大值是 5,000,000
const int MAXN = 5000000;

// spf[i] 数组，用来存放 i 的最小质因子 (Smallest Prime Factor)
int spf[MAXN + 1];

// omega_val[i] 数组，存放 i 的质因数总个数 (Ω(i))
int omega_val[MAXN + 1];

// prefix_sum_omega[i] 数组，存放 Ω(k) 从 k=1 到 i 的前缀和
long long prefix_sum_omega[MAXN + 1];

// 预处理函数，把上面三个数组都填满~
void precompute() {
    // 步骤一：用类似埃氏筛的方法计算每个数的最小质因子 (spf)
    // 先假设每个数的最小质因子都是它自己
    for (int i = 1; i <= MAXN; ++i) {
        spf[i] = i;
    }

    // 开始筛！从2开始，因为2是最小的质数
    for (int i = 2; i * i <= MAXN; ++i) {
        // 如果i的最小质因子是它自己，说明i是一个质数
        if (spf[i] == i) {
            // 那么i的倍数j的最小质因子就可能是i
            for (int j = i * i; j <= MAXN; j += i) {
                // 如果j的最小质因子还没被找到，就把它记为i
                if (spf[j] == j) {
                    spf[j] = i;
                }
            }
        }
    }

    // 步骤二：用动态规划的方式计算 Ω(i)
    // Ω(i) = Ω(i / spf[i]) + 1
    omega_val[1] = 0; // 1没有质因子，所以是0
    for (int i = 2; i <= MAXN; ++i) {
        // i的质因数个数 = (i除以其最小质因子后剩下的数)的质因数个数 + 1
        omega_val[i] = omega_val[i / spf[i]] + 1;
    }

    // 步骤三：计算 Ω(i) 的前缀和
    // prefix_sum_omega[i] = Σ_{k=1 to i} omega_val[k]
    prefix_sum_omega[0] = 0;
    for (int i = 1; i <= MAXN; ++i) {
        prefix_sum_omega[i] = prefix_sum_omega[i - 1] + omega_val[i];
    }
}

int main() {
    // 开启高速模式！
    fast_io();

    // 在处理查询之前，先进行一次性预计算
    precompute();

    int t;
    std::cin >> t;
    while (t--) {
        int a, b;
        std::cin >> a >> b;
        
        // 游戏得分是 Σ_{i=b+1 to a} Ω(i)
        // 利用前缀和，这个值等于 (Σ_{i=1 to a} Ω(i)) - (Σ_{i=1 to b} Ω(i))
        long long result = prefix_sum_omega[a] - prefix_sum_omega[b];
        std::cout << result << "\n";
    }

    return 0;
}

复杂度分析喵~ ​

  • 时间复杂度: O(N log log N + T) 的说。

    • 预处理是主要的时间开销。其中，计算spf数组的筛法部分，时间复杂度是 O(N log log N)，这里 N 是 MAXN。
    • 之后计算 omega_val 和 prefix_sum_omega 都是 O(N) 的线性扫描。
    • 所以预处理总时间是 O(N log log N)。
    • 对于 T 次查询，每次查询都只是数组的减法，是 O(1) 的。
    • 所以总时间复杂度就是 O(N log log N + T)。对于这道题的数据范围，完全足够快啦！

  • 空间复杂度: O(N) 的说。

    • 我们需要三个大小为 MAXN+1 的数组：spf、omega_val 和 prefix_sum_omega。所以空间开销是 O(N)，这也是可以通过的。

知识点与总结 ​

这道题真是太棒了，融合了好多数论和算法的知识点呢！让本喵来总结一下吧：

  1. 核心洞察: 将“最大游戏轮数”这个问题转化为计算质因数总数 Ω(n)，是解题的第一步，也是最关键的一步！
  2. 数论性质: 巧妙运用了 Ω(x * y) = Ω(x) + Ω(y) 这个性质，将 Ω(a! / b!) 展开成一个级数求和 Σ Ω(i)。
  3. 预处理思想: 面对多组查询和大数据范围，要立刻想到“预处理”！一次计算，多次使用，是应对这类问题的万能钥匙喵。
  4. 筛法应用: 线性筛或者类埃氏筛是预处理数论函数（比如最小质因子、欧拉函数、莫比乌斯函数等）的强大工具。本题的 spf 筛就是一个经典应用。
  5. 动态规划: Ω(i) = Ω(i / spf[i]) + 1 这个递推式本质上是一种动态规划思想，利用已解出的子问题（Ω(i / spf[i])）来求解当前问题（Ω(i)）。
  6. 前缀和: 这是将“范围查询”转化为 O(1) 操作的经典技巧。一旦问题可以表示为某个序列的区间和，前缀和就是不二之选！

希望这篇题解能帮助到你哦~ 如果还有不懂的地方，随时可以再来问本喵！一起加油，成为算法大师吧！喵~ (๑•̀ㅂ•́)و✧

Released under the MIT License.

Copyright © 2024-present Moe