G. D-Function - 题解

比赛与标签

比赛: Codeforces Round 952 (Div. 4) 标签: combinatorics, math, number theory 难度: *1600

题目大意喵~

这道题呀，是关于数字和的有趣问题呢！

首先，我们定义一个函数 D(n)，它表示正整数 n 的各位数字之和。比如说，D(123) = 1 + 2 + 3 = 6 的说。

题目会给我们三个整数 l, r 和 k。我们需要找出，在 10^l <= n < 10^r 这个范围里，有多少个整数 n 能够满足一个神奇的条件：D(k * n) = k * D(n)。

因为答案可能会很大，所以我们需要把最终的数量对 10^9 + 7 取模哦。

简单来说，就是：

输入: t 组测试数据，每组包含 l, r, k。
任务: 找到在 [10^l, 10^r) 区间内，满足 D(k * n) = k * D(n) 的 n 的个数。
输出: 个数模 10^9 + 7。

解题思路喵！

嘿嘿，这个问题看起来有点神秘，D(k * n) = k * D(n) 这个等式到底藏着什么小秘密呢？让本猫娘来揭晓吧！喵~

我们来想一想，什么时候做乘法不会改变“各位数字和”的结构呢？

举个栗子！n = 12, D(n) = 3。

如果 k = 4，那么 k * n = 48，D(k * n) = 12。而 k * D(n) = 4 * 3 = 12。哇，它们相等了！
如果 k = 5，那么 k * n = 60，D(k * n) = 6。而 k * D(n) = 5 * 3 = 15。不等了呢！

区别在哪里呀？关键就在于进位！

当我们在做小学乘法 12 * 4 时，我们是这样算的：

4 * 2 = 8
4 * 1 = 4
结果是 48。在这个过程中，每一位的乘积都没有超过9，所以没有发生进位。

而 12 * 5 呢：

5 * 2 = 10。这里就产生了一个进位！个位的 0 留下了，1 跑到了十位去。
5 * 1 = 5，再加上进位的 1，变成了 6。
结果是 60。

当没有进位发生时，k * n 的各位数字之和，就等于 n 的每一位数字与 k 相乘后，再把结果的各位数字加起来。如果 k 乘上 n 的每一位数字 d_i 之后，结果 k * d_i 本身仍然是一个个位数（即 k * d_i <= 9），那么 D(k * n) 就会等于 k * D(n) 啦！

所以，那个神秘的等式 D(k * n) = k * D(n) 成立的充要条件是： 对于 n 的每一个数字 d，都必须满足 k * d <= 9。

这一下子就把问题变得超级简单了，对吧！我们不再需要关心 n 的具体值，只需要关心它的每一位数字满足什么条件。

从 k * d <= 9，我们可以得到 d <= 9 / k（这里是整数除法）。设 max_digit = 9 / k。那么，一个数 n 如果要满足题意，它的每一位数字都必须在 0 到 max_digit 的范围里。

现在问题就转化成了一个计数问题： 在 [10^l, 10^r) 范围内，有多少个数的所有位数都小于等于 max_digit？

这个问题我们可以用一种叫做“前缀和”的思想来解决，喵~

我们先计算出在 [1, 10^r) 范围内有多少个满足条件的数。
再计算出在 [1, 10^l) 范围内有多少个满足条件的数。
两者相减，就是 [10^l, 10^r) 范围内的答案啦！

那么，怎么计算 [1, 10^x) 范围内满足条件的数的个数呢？一个数 n < 10^x，意味着它最多有 x 位。我们可以把它看成一个长度为 x 的数字串（不足的前面补 0）。

每一位都有 max_digit + 1 种选择（从 0 到 max_digit）。
设 base = max_digit + 1。
那么，x 位数，每一位都有 base 种选择，总共就有 base^x 种组合。
这些组合里包含了一个全 0 的情况，也就是数字 0。题目中的 n 是正整数，所以要把它排除掉。
所以，在 [1, 10^x) 范围内，满足条件的数的个数是 base^x - 1。

根据上面的推导：

[1, 10^r) 中满足条件的个数是 base^r - 1。
[1, 10^l) 中满足条件的个数是 base^l - 1。

所以，在 [10^l, 10^r) 中满足条件的个数就是： (base^r - 1) - (base^l - 1) = base^r - base^l

因为 r 和 l 可能非常大，我们不能直接计算 base^r。这时候就需要用到我们的好朋友——快速幂算法，来计算 (base^r % M) 和 (base^l % M)。

最终的答案就是 (power(base, r) - power(base, l) + M) % M。+ M 是为了防止减法出现负数哦。

代码实现喵~

下面就是把我们的思路变成代码啦！注释里有更详细的解释哦~

cpp

#include <iostream>

// 这个函数是用来计算 (base^exp) % mod 的，也就是快速幂喵~
// 对于指数很大的情况，这个算法超级快！
long long power(long long base, long long exp) {
    long long res = 1;
    long long M = 1000000007; // 这是我们可爱的模数
    base %= M;
    while (exp > 0) {
        // 如果指数是奇数，就把当前的 base 乘到结果里
        if (exp % 2 == 1) {
            res = (res * base) % M;
        }
        // base 自己平方，为下一轮做准备
        base = (base * base) % M;
        // 指数除以 2
        exp /= 2;
    }
    return res;
}

void solve() {
    long long l, r, k;
    std::cin >> l >> r >> k;

    // 关键的第一步！根据 D(k*n) = k*D(n) 的性质，
    // 我们知道 n 的每一位数字 d 都必须满足 k*d <= 9。
    // 所以，数字的最大值就是 9/k (整数除法)。
    long long max_digit = 9 / k;
    
    // 每一位数字可以从 0, 1, ..., max_digit 中选择。
    // 所以总共有 max_digit + 1 种选择。我们把它叫做 base。
    long long base = max_digit + 1;
    
    long long M = 1000000007;

    // 我们要计算在 [10^l, 10^r) 范围内的合法数字数量。
    // 这等价于 (小于 10^r 的合法数) - (小于 10^l 的合法数)。
    //
    // 小于 10^x 的合法正整数数量是 base^x - 1。
    // 所以，答案就是 (base^r - 1) - (base^l - 1) = base^r - base^l。
    // 我们用快速幂来计算这两项。
    
    long long term_r = power(base, r);
    long long term_l = power(base, l);
    
    // 计算 (term_r - term_l)，并且处理好负数的情况。
    long long ans = (term_r - term_l + M) % M;
    
    std::cout << ans << std::endl;
}

int main() {
    // 加速输入输出，让程序跑得飞快~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

复杂度分析的说

时间复杂度: O(log r) 的说。对于每一组测试数据，我们主要的计算量是两次快速幂。快速幂算法的时间复杂度是 O(log(指数))。因为 r 是指数中较大的那个，所以时间复杂度是 O(log r)。总时间复杂度就是 O(T * log r)，其中 T 是测试数据组数，非常高效！
空间复杂度: O(1) 的说。我们只用了几个变量来存 l, r, k 和一些中间结果，没有使用额外的数组或者数据结构，所以空间消耗是常数级别的。

知识点与总结喵~

这道题真是太棒啦，让我们学到了好多东西！

核心洞察力: 解决问题的关键在于将 D(k * n) = k * D(n) 这个看似复杂的数论性质，转化为一个非常直观的条件——乘法不产生进位。这告诉我们，遇到关于数字和的问题时，一定要思考进位这个小淘气带来的影响！
化繁为简: 一旦找到了核心性质，问题就从一个复杂的数论问题变成了一个简单的组合计数问题。这就是算法的魅力所在，喵~
计数技巧: 对于 [A, B) 这样的区间计数问题，使用 count(B) - count(A) 的“前缀和”思想是一个非常常用且强大的技巧。
快速幂: 只要题目中出现了 a^b % M 并且 b 还特别大，那就要立刻想到快速幂！它是处理大指数模幂问题的标准武器。

希望这篇题解能帮助到大家！只要我们善于发现问题背后的简单规律，再难的题目也能迎刃而解的！大家要继续加油哦，喵~！

G. D-Function - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路喵！ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结喵~ ​