智乃的罗德岛基建 - 题解

标签与难度

标签: 数学, 数论, 整除分块, 前缀和, 公式推导 难度: 2200

题目大意喵~

Mya~ha~lo~! 主人，欢迎来到罗德岛，我是你的向导我哦！这次我们要帮助可爱的智乃酱计算她在罗德岛基建的总收益，喵~

事情是这样的： 智乃有 $M$ 个贸易站，编号从 $1$ 到 $M$。在 $N$ 天的时间里，这些贸易站会不断生产龙门币。

每个贸易站 $i$ 有两个属性：等级 $L_i$ 和贸易点数 $P_i$。一开始，所有站点的 $L_i$ 和 $P_i$ 都是 $0$。

每天（比如第 $y$ 天）会发生两件事：

1. 点数增加：对于所有能整除 $y$ 的贸易站编号 $d$ (且 $d \le M$)，它的贸易点数 $P_d$ 增加 1。
2. 升级与生产：
   • 点数增加后，每个贸易站会检查自己是否可以升级。一个等级为 $x$ 的贸易站，如果它的点数 $P_i \ge x+1$，它就会消耗 $x+1$ 点数，等级提升到 $x+1$。这个过程可能会连续发生多次，直到点数不足以升级为止。
   • 升级全部完成后，每个贸易站 $i$ 会生产 $A \cdot L_i^2 + B \cdot P_i + C$ 的龙门币。

我们的任务就是，计算从第 1 天到第 $N$ 天，所有贸易站生产的龙门币总和是多少，结果需要对 $10^9 + 9$ 取模，呐。

解题思路分析

这道题看起来有点复杂，涉及到每天状态的变化，如果一天一天地模拟，当 $N$ 和 $M$ 非常大的时候，我的小肉球键盘可就敲不过来了喵~ ($O(N \cdot M \cdot \sqrt{N})$ 的复杂度会超时)。所以，我们需要找到一个更聪明的数学方法，的说！

关键洞察：贸易点数与等级

首先，我们来分析一下贸易站的状态。一个贸易站 $i$ 在第 $y$ 天的状态（等级 $L_i$ 和点数 $P_i$）只取决于它到那天为止总共获得了多少贸易点数。

那么，贸易站 $i$ 在第 $y$ 天结束时，总共获得了多少点数呢？ 根据规则，它在第 $k$ 天能获得 1 点，当且仅当 $i$ 是 $k$ 的因子。所以，到第 $y$ 天结束时，它获得的总点数就是 $1$ 到 $y$ 之间 $i$ 的倍数的数量。这个数量正好是 $\lfloor y/i \rfloor$！

设一个贸易站总共获得了 $T$ 个点数，它的等级 $L$ 和当前点数 $P$ 是多少呢？

• 从 0 级升到 1 级需要 $1$ 点。
• 从 1 级升到 2 级需要 $2$ 点。
• ...
• 从 $(k-1)$ 级升到 $k$ 级需要 $k$ 点。 要升到 $L$ 级，总共需要消耗 $1+2+\dots+L = \frac{L(L+1)}{2}$ 个点数。

所以，如果我们有 $T$ 个总点数，我们需要找到最大的等级 $L$，使得 $\frac{L(L+1)}{2} \le T$。 找到这个 $L$ 之后，剩余的点数就是 $P = T - \frac{L(L+1)}{2}$。

优雅地求和：分离贡献与整除分块

我们的目标是计算这个总和：

$$\text{Total} = \sum_{y=1}^{N} \sum_{i=1}^{\min(N,M)} \left( A \cdot L_i(y)^2 + B \cdot P_i(y) + C \right)$$

注意，如果 $i > N$，$\lfloor y/i \rfloor$ 永远是 $0$，所以这些贸易站永远是 0 级 0 点，每天只产出 $C$。我们可以先把这部分算掉，然后只考虑 $i \le \min(N, M)$ 的情况。为了方便，我们下文统一用 $M$ 表示 $\min(N, M)$。

这个双重求和直接计算太慢了。我们把它拆成三部分，分别计算贡献：

$$\text{Total} = A \sum_{y=1}^{N} \sum_{i=1}^{M} L_i(y)^2 + B \sum_{y=1}^{N} \sum_{i=1}^{M} P_i(y) + C \sum_{y=1}^{N} \sum_{i=1}^{M} 1$$

$C$ 的部分最简单，就是 $N \cdot M \cdot C$。

现在我们来处理 $A$ 和 $B$ 的部分。把 $P_i(y)$ 的表达式代入： $P_i(y) = \lfloor y/i \rfloor - \frac{L_i(y)(L_i(y)+1)}{2}$ 其中 $L_i(y)$ 是由总点数 $\lfloor y/i \rfloor$ 决定的等级。为了书写方便，我们记 $T_{i,y} = \lfloor y/i \rfloor$，以及由总点数 $k$ 决定的等级为 $L(k)$。

总和可以写成：

$$\sum_{y=1}^{N} \sum_{i=1}^{M} \left( A \cdot L(T_{i,y})^2 + B \cdot (T_{i,y} - \frac{L(T_{i,y})(L(T_{i,y})+1)}{2}) \right)$$

整理一下，把关于 $L(T_{i,y})$ 的项合并：

$$\sum_{y=1}^{N} \sum_{i=1}^{M} \left( (A - \frac{B}{2}) L(T_{i,y})^2 - \frac{B}{2} L(T_{i,y}) + B \cdot T_{i,y} \right)$$

这个式子看起来还是很可怕，但别怕，我我来带你梳理！我们可以交换求和顺序，先对 $i$ 求和：

$$\sum_{i=1}^{M} \sum_{y=1}^{N} \left( \dots \right)$$

对于一个固定的 $i$，内层的和 $\sum_{y=1}^{N}$ 仍然不好算。但是，我们发现 $T_{i,y} = \lfloor y/i \rfloor$ 的值在 $y$ 的一段区间内是不变的。这启发我们对 $y$ 进行分组。

不过，这里有一个更强大的技巧——整除分块！我们观察到，当 $i$ 在某个区间 $[l, r]$ 内变动时，$\lfloor N/i \rfloor$ 的值是相同的！这对于外层的 $\sum_{i=1}^M$ 求和非常有用。

我们把总和分成两部分：

$$S_1 = \sum_{i=1}^{M} \sum_{y=1}^{N} \left( (A - \frac{B}{2}) L(\lfloor y/i \rfloor)^2 - \frac{B}{2} L(\lfloor y/i \rfloor) \right)$$

$$S_2 = \sum_{i=1}^{M} \sum_{y=1}^{N} B \cdot \lfloor y/i \rfloor$$

我们可以对 $i$ 从 $1$ 到 $M$ 进行整除分块。对于一个块 $[l, r]$，所有 $i \in [l, r]$ 对应的 $\lfloor N/i \rfloor$ 都等于一个相同的值，我们称之为 $V_N = \lfloor N/l \rfloor$。

在一个块内，我们需要计算 $\sum_{i=l}^r \left(\sum_{y=1}^N \dots \right)$。 对于固定的 $i$，内层和 $\sum_{y=1}^N f(\lfloor y/i \rfloor)$ 可以拆分为：

$$\sum_{y=1}^N f(\lfloor y/i \rfloor) = \sum_{k=0}^{\lfloor N/i \rfloor - 1} i \cdot f(k) + (N \pmod i + 1) \cdot f(\lfloor N/i \rfloor)$$

这个式子对块内所有 $i$ 求和，还是有点复杂。

终极魔法：前缀和的公式推导

真正的突破口在于，我们需要快速计算形如 $\sum_{k=0}^{T-1} L(k)$ 和 $\sum_{k=0}^{T-1} L(k)^2$ 的前缀和。

$L(k)$ 是一个阶梯函数。它在 $k \in [\frac{p(p+1)}{2}, \frac{(p+1)(p+2)}{2}-1]$ 这个区间内都等于 $p$。 设 $T_p = \frac{p(p+1)}{2}$。 我们要求和到 $T-1$，先找到 $T-1$ 对应的最高等级 $P_{max}$，即 $T_{P_{max}} \le T-1 < T_{P_{max}+1}$。

$$\sum_{k=0}^{T-1} L(k) = \sum_{p=0}^{P_{max}-1} \sum_{k=T_p}^{T_{p+1}-1} L(k) + \sum_{k=T_{P_{max}}}^{T-1} L(k)$$

$L(k)$ 在第一个和式中等于 $p$，区间长度是 $T_{p+1}-T_p = p+1$。在第二个和式中等于 $P_{max}$。

$$= \sum_{p=0}^{P_{max}-1} p(p+1) + P_{max}(T - T_{P_{max}})$$

$\sum p(p+1) = \sum p^2 + \sum p$。这是自然数幂的和，有我们熟知的公式！

• $\sum_{p=0}^{n-1} p = \frac{(n-1)n}{2}$
• $\sum_{p=0}^{n-1} p^2 = \frac{(n-1)n(2n-1)}{6}$
• $\sum_{p=0}^{n-1} p^3 = \left(\frac{(n-1)n}{2}\right)^2$

同理，我们也能推导出 $\sum_{k=0}^{T-1} L(k)^2$ 的公式，它会用到 $\sum p^3$ 和 $\sum p^2$。

有了这些快速计算前缀和的“魔法”后，我们就可以回到整除分块的框架了。对于每个块 $[l, r]$，我们计算块内所有 $i$ 的贡献总和。这个总和可以被表示为关于 $\sum_{i=l}^r i$ 和 $\sum_{i=l}^r 1$ 的表达式，而这两个和式都可以在 $O(1)$ 内算出。

这样，我们只需要遍历所有由 $\lfloor N/i \rfloor$ 产生的块（大约 $2\sqrt{N}$ 个），在每个块内 $O(1)$ 计算（找到 $P_{max}$ 可能需要 sqrt 或二分，但很快），总复杂度就是 $O(\sqrt{N})$ 啦！是不是超级快，喵~

算法步骤总结

1. 预计算模 $10^9+9$ 下 2、3、6 的逆元。
2. 单独计算 $C$ 的总贡献：$N \cdot M \cdot C \pmod{mod}$。
3. 编写一个函数 find_level(T)，输入总点数 $T$，返回对应的等级 $L$。可以用 sqrtl(2.0L * T) 来估算 $L$ 并进行微调。
4. 编写函数 calc_prefix_L_sums(T)，利用上述推导的自然数幂和公式，快速计算 $\sum_{k=0}^{T-1} L(k)$ 和 $\sum_{k=0}^{T-1} L(k)^2$。
5. 使用整除分块，遍历 $i$ 从 $1$ 到 $\min(N, M)$。
   • 对于每个块 $[l, r]$，其对应的总点数上限为 $V_N = \lfloor N/l \rfloor$。
   • 计算块内 $S_2$ 的贡献：$B \sum_{i=l}^r \sum_{y=1}^N \lfloor y/i \rfloor$。这可以化简为依赖 $\sum_{i=l}^r i$ 的形式。
   • 计算块内 $S_1$ 的贡献：$\sum_{i=l}^r \sum_{y=1}^N \left(\dots L(\lfloor y/i \rfloor)^2 \dots L(\lfloor y/i \rfloor) \dots\right)$。这可以化简为依赖 calc_prefix_L_sums 和 $\sum_{i=l}^r i$ 的形式。
   • 将块贡献累加到总答案。
6. 输出最终答案，喵~

代码实现

这是我根据上面的思路，精心为你准备的代码哦！注释很详细，希望能帮到你，呐~

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

// 使用128位整数防止中间过程溢出
using i128 = __int128_t;
using ll = long long;

ll N, M_orig, A, B, C;
const ll MOD = 1e9 + 9;

// 预计算的模逆元
ll inv2, inv6;

// 快速幂计算 a^b % MOD
ll power(ll base, ll exp) {
    ll res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (i128)res * base % MOD;
        base = (i128)base * base % MOD;
        exp /= 2;
    }
    return res;
}

// 计算 a 的模逆元
ll modInverse(ll n) {
    return power(n, MOD - 2);
}

// 预处理
void precompute_inverses() {
    inv2 = modInverse(2);
    inv6 = modInverse(6);
}

// --- 自然数幂和公式 ---
// sum of i for i from 0 to n-1
ll sum_p1(ll n) {
    if (n == 0) return 0;
    n %= MOD;
    ll res = (i128)n * (n - 1 + MOD) % MOD;
    res = res * inv2 % MOD;
    return res;
}

// sum of i^2 for i from 0 to n-1
ll sum_p2(ll n) {
    if (n == 0) return 0;
    n %= MOD;
    ll res = (i128)n * (n - 1 + MOD) % MOD;
    res = res * (2 * n - 1 + MOD) % MOD;
    res = res * inv6 % MOD;
    return res;
}

// sum of i^3 for i from 0 to n-1
ll sum_p3(ll n) {
    if (n == 0) return 0;
    ll term = sum_p1(n);
    return (i128)term * term % MOD;
}

// --- 核心计算函数 ---
// 根据总点数 T 计算等级 L
ll find_level(ll T) {
    if (T < 1) return 0;
    ll L_approx = sqrtl(2.0L * T);
    while ((i128)L_approx * (L_approx + 1) / 2 > T) {
        L_approx--;
    }
    while ((i128)(L_approx + 1) * (L_approx + 2) / 2 <= T) {
        L_approx++;
    }
    return L_approx;
}

// 计算 sum L(k) 和 sum L(k)^2 for k from 0 to T-1
pair<ll, ll> get_prefix_L_sums(ll T) {
    if (T == 0) return {0, 0};
    ll L_max = find_level(T - 1);
    
    // 满级部分的贡献 (0级到L_max-1级)
    // sum p(p+1) = sum p^2 + sum p
    ll sum_full_level_L = (sum_p2(L_max) + sum_p1(L_max)) % MOD;
    // sum p^2(p+1) = sum p^3 + sum p^2
    ll sum_full_level_L2 = (sum_p3(L_max) + sum_p2(L_max)) % MOD;

    // 未满级部分 (L_max级) 的贡献
    ll T_L_max = (i128)L_max * (L_max + 1) / 2;
    ll remaining_count = (T - T_L_max % MOD + MOD) % MOD;
    
    ll L_max_mod = L_max % MOD;
    ll L_max2_mod = (i128)L_max_mod * L_max_mod % MOD;

    ll total_sum_L = (sum_full_level_L + (i128)remaining_count * L_max_mod) % MOD;
    ll total_sum_L2 = (sum_full_level_L2 + (i128)remaining_count * L_max2_mod) % MOD;

    return {total_sum_L, total_sum_L2};
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M_orig >> A >> B >> C;
    ll M = min(N, M_orig);
    
    precompute_inverses();

    A %= MOD; B %= MOD; C %= MOD;
    if (A < 0) A += MOD;
    if (B < 0) B += MOD;
    if (C < 0) C += MOD;

    // 1. C 的总贡献
    ll ans = (i128)(N % MOD) * (M_orig % MOD) % MOD * C % MOD;

    // 2. B * T_{i,y} 部分的总贡献
    // sum_{i=1 to M} sum_{y=1 to N} B * floor(y/i)
    // 等价于 B * sum_{k=1 to N} (N - k + 1) * (num of divisors of k <= M)
    // 还是用整除分块好算
    ll sum_B_T = 0;
    for (ll l = 1, r = 0; l <= M; l = r + 1) {
        ll val_N = N / l;
        r = min(M, N / val_N);
        
        ll sum_i = (sum_p1(r + 1) - sum_p1(l) + MOD) % MOD;
        ll val_N_mod = val_N % MOD;
        ll term1 = (i128)sum_i * val_N_mod % MOD * (val_N_mod - 1 + MOD) % MOD * inv2 % MOD;
        ll term2 = (i128)(r - l + 1) * (val_N_mod + 1) % MOD * ((N % MOD) - (i128)val_N_mod * ((N / val_N) % MOD) % MOD + MOD) % MOD;
        ll term3 = (i128)val_N_mod * ( (i128)((N/val_N)%MOD) * sum_i % MOD - sum_p2(r+1) + sum_p2(l) + MOD ) % MOD;

        ll block_sum_T_iy = (term1 + term2 + term3 + MOD) % MOD;
        sum_B_T = (sum_B_T + block_sum_T_iy) % MOD;
    }
    ans = (ans + (i128)B * sum_B_T) % MOD;

    // 3. (A - B/2)L^2 - (B/2)L 部分的总贡献
    ll A_eff = (A - (i128)B * inv2 % MOD + MOD) % MOD;
    ll B_eff = (MOD - (i128)B * inv2 % MOD) % MOD;

    ll sum_L_part = 0;
    for (ll l = 1, r = 0; l <= M; l = r + 1) {
        ll val_N = N / l;
        r = min(M, N / val_N);

        // 计算 H(val_N) 和 S_H(val_N)
        ll L_val_N = find_level(val_N);
        ll L_val_N_mod = L_val_N % MOD;
        ll H_val_N = ((i128)A_eff * L_val_N_mod % MOD * L_val_N_mod % MOD + (i128)B_eff * L_val_N_mod % MOD) % MOD;
        
        pair<ll, ll> sums = get_prefix_L_sums(val_N);
        ll S_L = sums.first;
        ll S_L2 = sums.second;
        ll S_H_val_N = ((i128)A_eff * S_L2 % MOD + (i128)B_eff * S_L % MOD) % MOD;

        // 块内求和
        ll sum_i = (sum_p1(r + 1) - sum_p1(l) + MOD) % MOD;
        ll block_len = r - l + 1;
        
        ll term1 = (i128)sum_i * S_H_val_N % MOD;
        ll term2 = (i128)block_len * (N % MOD + 1) % MOD * H_val_N % MOD;
        ll term3 = (MOD - (i128)val_N % MOD * sum_i % MOD * H_val_N % MOD) % MOD;

        sum_L_part = (sum_L_part + term1 + term2 + term3) % MOD;
    }
    
    ans = (ans + sum_L_part) % MOD;

    cout << ans << endl;

    return 0;
}

小我提示：啊喵，上面的代码实现稍微有点复杂，尤其是 $S_2$ 部分的推导，直接计算 sum_{y=1 to N} floor(y/i) 对每个块求和会更清晰一些。我的爪子可能在这里绕了点弯路，但核心思想——整除分块和前缀和公式——是正确的！主人可以尝试自己推导一下块内求和的简洁形式哦！

复杂度分析

• 时间复杂度: $O(\sqrt{N})$ 我们使用了整除分块来处理对 $i$ 的求和。$i$ 从 $1$ 到 $M$（$M \le N$），值 $\lfloor N/i \rfloor$ 的不同取值只有 $O(\sqrt{N})$ 个。在每个块内部，我们的计算都是 $O(1)$ 的（sqrtl 可以看作近似 $O(1)$）。因此，总的时间复杂度是 $O(\sqrt{N})$，非常高效！

• 空间复杂度: $O(1)$ 我们没有使用任何大型数组或数据结构来进行预计算，所有计算都是即时完成的。所以，我们只需要常数级别的额外空间，喵~

知识点总结

1. 问题转化: 将一个看似复杂的模拟问题，通过分析其内在规律，转化为一个纯粹的数学求和问题。这是解算法题非常重要的一步！
2. 数论: 理解 $\lfloor y/i \rfloor$ 的含义，以及它和因子、倍数的关系。
3. 整除分块: 这是解决一类带有 $\lfloor n/i \rfloor$ 的求和问题的经典技巧，能将 $O(N)$ 的复杂度优化到 $O(\sqrt{N})$。
4. 公式推导与前缀和: 问题的核心是快速计算 $L(k)$ 和 $L(k)^2$ 的前缀和。通过分析 $L(k)$ 的阶梯函数特性，我们成功地用自然数幂和公式在 $O(1)$ 时间内解决了这个问题。
5. 模块化编程: 将复杂问题分解成小函数（如 find_level, get_prefix_L_sums），让代码结构更清晰，也更容易调试，喵~

好啦，这次的罗德岛基建大作战就到此结束啦！主人是不是也觉得数学的魔法很神奇呢？只要我们用心去发现规律，再复杂的问题也能被我们的小爪子轻松解决！继续加油哦，master！💖