Dividing - 题解

标签与难度

标签: 数论, 整除分块, 数学, 组合计数, 推理难度: 1600

题目大意喵~

你好呀，未来的算法大师！本喵今天带来了一道有趣的题目，叫做 "Dividing"。

题目定义了一种叫做“传奇元组” (n, k) 的东西，它遵循三条神秘的规则：

基础规则: 对于任何整数 k，(1, k) 都是一个传奇元组。这是我们所有变化的起点哦！
加法规则: 如果 (n, k) 是一个传奇元组，那么 (n + k, k) 也是一个传奇元组。
乘法规则: 如果 (n, k) 是一个传奇元组，那么 (nk, k) 也是一个传奇元组。

我们的任务是，给定两个正整数 N 和 K，计算出在 1 ≤ n ≤ N 和 1 ≤ k ≤ K 的范围内，总共有多少个不同的传奇元组 (n, k) 呢？

因为答案可能会非常大，所以我们需要将最终结果对 $10^9 + 7$ 取模，喵~

解题思路分析

喵哈哈，看到这种递归定义的规则，是不是感觉有点小复杂呀？别担心，跟着本喵的思路，一步步揭开它的神秘面纱！

关键性质的发现

我们先固定一个 k，看看对于这个 k，哪些 n 可以和它组成传奇元组。

规则告诉我们，一切都从 (1, k) 开始。

加法规则：从 (1, k) 出发，我们可以不断地加上 k，得到 (1+k, k), (1+2k, k), (1+3k, k), ... 这样，所有满足 n ≡ 1 (mod k) 的 n 都可以和 k 组成传奇元组。
乘法规则：从 (1, k) 出发，我们可以用乘法得到 (1*k, k)，也就是 (k, k)。这是一个新的起点！

现在我们有了 (k, k)，再对它应用规则：

加法规则：从 (k, k) 出发，我们可以得到 (k+k, k), (k+2k, k), ... 也就是 (2k, k), (3k, k), ... 这样，所有满足 n ≡ 0 (mod k) 的 n 也都可以和 k 组成传奇元组。

那么，是不是只有这两种情况呢？让我们来验证一下！我们可以反过来想：一个传奇元组 (n, k) 是如何生成的？它必然是由另一个传奇元tuple (n', k) 通过 n' + k 或者 n' * k 得到的。这意味着，我们可以通过“逆操作”——n-k 和 n/k——将任何一个传奇元组 (n, k) 追溯回 (1, k).

如果 k 能整除 n (即 k | n)，我们可以认为 n 是通过 (n/k, k) 乘以 k 得到的，或者通过 (n-k, k) 加上 k 得到的。
如果 n 除以 k 的余数是 1 (即 n ≡ 1 (mod k)), 我们可以认为 n 是通过 (n-k, k) 加上 k 得到的。

经过一番严谨的数学归纳（本喵在这里就省略掉枯燥的证明啦，但思路就是这样！），我们可以得出一个超级漂亮的结论：

一个元组 (n, k) 是传奇元组，当且仅当 k 整除 n 或者 k 整除 (n-1)。

是不是一下子就清晰多啦？问题被转化成了一个纯粹的计数问题！

转化为计数问题

我们要计算满足下面条件的数对 (n, k) 的数量：

1 ≤ n ≤ N
1 ≤ k ≤ K
k | n 或 k | (n-1)

这是一个集合求并集的问题，我们可以使用容斥原理来解决，喵~ 设 S1 是满足 k | n 的数对集合，S2 是满足 k | (n-1) 的数对集合。我们要求的就是 $|S1 \cup S2|$ 。根据容斥原理：

|S1 \cup S2| = |S1| + |S2| - |S1 \cap S2|

现在我们来分别计算这三部分：

计算 $|S1|$ |S1| 是满足 k | n 的数对数量。我们可以遍历所有可能的 k（从 1 到 K），对于每个 k，计算有多少个 n（从 1 到 N）是它的倍数。这个数量就是 $\lfloor N/k \rfloor$ 。所以：
$|S1| = \sum_{k=1}^{K} \lfloor \frac{N}{k} \rfloor$
计算 $|S2|$ |S2| 是满足 k | (n-1) 的数对数量。n 的范围是 [1, N]，所以 n-1 的范围是 [0, N-1]。对于每个 k，我们要计算在 [0, N-1] 中有多少个数是 k 的倍数。这些倍数是 0*k, 1*k, 2*k, ...。最大的倍数不能超过 N-1，所以倍数的数量是 $\lfloor \frac{N-1}{k} \rfloor + 1$ （因为要算上 0）。所以：
$|S2| = \sum_{k=1}^{K} \left( \lfloor \frac{N-1}{k} \rfloor + 1 \right) = \left( \sum_{k=1}^{K} \lfloor \frac{N-1}{k} \rfloor \right) + K$
计算 $|S1 \cap S2|$ |S1 \cap S2| 是同时满足 k | n 和 k | (n-1) 的数对数量。如果 k 同时整除 n 和 n-1，那么它一定能整除它们的差，也就是 n - (n-1) = 1。唯一能整除 1 的正整数 k 就是 1。所以，交集只在 k=1 时出现。当 k=1 时，1 | n 和 1 | (n-1) 对任何整数 n 都成立。因此，交集中的数对是 (n, 1)，其中 1 ≤ n ≤ N。这样的数对总共有 N 个。所以：
$|S1 \cap S2| = N$

最终公式与优化

把三部分合起来，总数就是：

\text{Total} = \left( \sum_{k=1}^{K} \lfloor \frac{N}{k} \rfloor \right) + \left( \left( \sum_{k=1}^{K} \lfloor \frac{N-1}{k} \rfloor \right) + K \right) - N

现在的问题就是如何快速计算 $\sum_{k=1}^{K} \lfloor \frac{N}{k} \rfloor$ 这种形式的和。如果 K 很大，一个一个 k 遍历相加肯定会超时的说。

这里就需要一个非常经典的数论技巧——整除分块！我们观察 $\lfloor N/k \rfloor$ 的值，会发现它在 k 连续的一段区间内是保持不变的。例如，当 N=10 时：

k=1, $\lfloor 10/1 \rfloor = 10$
k=2, $\lfloor 10/2 \rfloor = 5$
k=3, $\lfloor 10/3 \rfloor = 3$
k=4, 5, $\lfloor 10/k \rfloor = 2$
k=6, 7, 8, 9, 10, $\lfloor 10/k \rfloor = 1$

我们可以把 k 分成一块一块的，每块的 $\lfloor N/k \rfloor$ 值都相同，然后一次性计算这一整块的贡献！

具体来说，如果我们当前在块的左端点 l，那么这个块的值是 v = N / l。这个块的右端点 r 是哪里呢？是最大的那个使得 N / r 仍然等于 v 的 r，也就是 r = N / v。所以，对于从 l 到 r 的所有 k， $\lfloor N/k \rfloor$ 的值都是 v。这个块的长度是 r - l + 1，它对总和的贡献就是 v * (r - l + 1)。计算完这个块后，下一个块的左端点就是 r + 1。我们不断重复这个过程，直到 l > K。

这个算法的复杂度大约是 $O(\sqrt{N} + \sqrt{K})$ ，对于很大的 N 和 K 也能轻松跑过，喵~

代码实现

这是本喵根据上面的思路，精心为你准备的C++代码，注释超详细的哦！

cpp

#include <iostream>

// 定义一个常量表示模数
const int MOD = 1e9 + 7;

/**
 * @brief 使用整除分块计算 sum_{i=1 to k_limit} floor(n_limit / i)
 * 
 * @param n_limit 公式中的 N
 * @param k_limit 求和的上界 K
 * @return long long 求和的结果 (对 MOD 取模)
 */
long long calculate_sum_floor(long long n_limit, long long k_limit) {
    if (n_limit < 0) { // 处理 n_limit 为 N-1 且 N=0 的情况
        return 0;
    }
    long long total_sum = 0;
    // 使用整除分块
    // l 是块的左边界, r 是块的右边界
    for (long long l = 1, r; l <= k_limit; l = r + 1) {
        // 如果 l > n_limit, 那么 n_limit / l 总是 0，可以提前结束
        if (l > n_limit) {
            break;
        }
        
        long long value = n_limit / l;
        // 计算当前块的右边界
        // r = n_limit / value 是使得 floor(n_limit / k) == value 的最大 k
        // 同时 r 不能超过求和的上界 k_limit
        r = std::min(k_limit, n_limit / value);
        
        // 计算当前块的长度
        long long count = (r - l + 1) % MOD;
        // 计算当前块对总和的贡献
        long long contribution = (value % MOD * count) % MOD;
        
        // 累加到总和
        total_sum = (total_sum + contribution) % MOD;
    }
    return total_sum;
}

int main() {
    // 提高输入输出效率
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    long long N, K;
    std::cin >> N >> K;

    // 根据公式计算 |S1| = sum_{k=1 to K} floor(N/k)
    long long sum1 = calculate_sum_floor(N, K);
    
    // 根据公式计算 |S2| 的一部分: sum_{k=1 to K} floor((N-1)/k)
    long long sum2_part1 = calculate_sum_floor(N - 1, K);
    
    // |S2| 的完整值
    long long sum2 = (sum2_part1 + K) % MOD;
    
    // 根据容斥原理计算总数
    // Total = |S1| + |S2| - |S1 ∩ S2|
    // Total = sum1 + sum2 - N
    long long ans = (sum1 + sum2) % MOD;
    ans = (ans - (N % MOD) + MOD) % MOD; // 减法要加上 MOD 防止出现负数

    std::cout << ans << std::endl;

    return 0;
}

复杂度分析

时间复杂度: $O(\sqrt{N} + \sqrt{K})$ 。我们的主要计算量在 calculate_sum_floor 函数中。整除分块的迭代次数，对于 calculate_sum_floor(n, k) 来说，大约是 $O(\min(\sqrt{n}, k))$ 。我们调用了两次，一次是 (N, K)，一次是 (N-1, K)。所以总的时间复杂度是 $O(\min(\sqrt{N}, K) + \min(\sqrt{N-1}, K))$ ，可以近似看作 $O(\sqrt{N} + \sqrt{K})$ 。
空间复杂度: $O(1)$ 。我们只使用了几个变量来存储中间结果，没有使用额外的数组或者数据结构，所以空间消耗是常数级别的，非常优秀的说！

知识点总结

这道题虽然看起来有点唬人，但其实是一次美妙的思维探险，喵~ 从中我们可以学到：

问题转化: 将复杂的递归定义规则，通过分析和归纳，转化为一个简洁的数论性质 (k|n 或 k|(n-1))。这是解决很多算法问题的关键一步！
容斥原理: 当遇到“或”关系的计数问题时，容斥原理是一个非常强大的工具。|A U B| = |A| + |B| - |A ∩ B| 这个公式要牢记在心哦。
整除分块: 这是数论问题中一个非常重要的优化技巧。当你要计算形如 $\sum_{i=1}^{n} \lfloor f(i) \rfloor$ 的和，并且 $\lfloor f(i) \rfloor$ 的值在连续区间内不变时，就可以考虑使用整除分块来加速计算。

希望本喵的题解能帮助你更好地理解这道题，继续加油，你超棒的！喵~

Dividing - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

关键性质的发现 ​

转化为计数问题 ​

最终公式与优化 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​