F. Interesting Function - 题解

比赛与标签

比赛: Codeforces Round 725 (Div. 3) 标签: binary search, dp, math, number theory 难度: *1500

题目大意喵~

主人，下午好呀！这道题是这样的喵~

我们有两个整数 l 和 r，然后我们要不停地给 l 加 1，直到它变成 r 为止。在这个过程中，每一次加 1，我们都要观察一下，有多少个数字位发生了变化。

举个栗子🌰：

如果 l = 909，加 1 之后变成 910。个位的 9 变成了 0，十位的 0 变成了 1，所以有 2 个数字位改变了。
如果 l = 9，加 1 之后变成 10。个位的 9 变成了 0，还多出了一个十位的 1，这也算 2 个数字位改变了。
如果 l = 489999，加 1 之后变成 490000，有 5 个数字位改变了呢！

我们的任务就是，把从 l 增加到 r 的过程中，每一次加法所导致的数字位变化数量全部加起来，得到一个总和。这就是我们要输出的答案啦，喵~

解题思路大揭秘！

这道题看起来是要我们模拟从 l 到 r 的每一次加法，然后数变化，但 r 最大可以到 10^9，直接模拟肯定会超时的说！所以，我们需要找到一个更聪明的办法，喵~

换个角度看问题

题目要求的是一个区间 [l, r-1] 上每个数 +1 后的变化总和。这种区间求和的问题，通常可以转换成“前缀和”的思想来解决，呐。

我们可以定义一个函数 F(n)，它表示从 1 开始，一直加到 n，这个过程中总共发生了多少次数字位变化。也就是 (0->1) + (1->2) + ... + ((n-1)->n) 的总变化数。

如果有了这个神奇的 F(n) 函数，那从 l 到 r 的总变化数就可以表示为： 总变化数(l, r) = F(r) - F(l)

为什么呢？因为 F(r) 是从 1 到 r 的总变化，F(l) 是从 1 到 l 的总变化。两者相减，剩下的不就是从 l+1 到 r 的变化了嘛，这正好对应了 l 到 r-1 这些数字加 1 之后的变化总和，完美！

如何计算 F(n) 呢？

现在的问题就变成了如何高效地计算 F(n)。我们不一个一个地数，而是从“贡献”的角度来思考，喵~

我们来分析一下，从 1 到 n，每个数位（个位、十位、百位...）总共变化了多少次。

个位 (10^0): 每次加 1，个位都会变（除非是 9->0 这种进位）。但其实我们可以认为，从 0 到 n，每次加 1 都导致了个位的变化。比如 1->2, 2->3... 9->0。所以，从 1 到 n，个位总共变化了 n 次。
十位 (10^1): 十位什么时候会变呢？只有在个位从 9 变成 0 的时候，才会发生进位，从而引起十位的变化。这发生在 9->10, 19->20, 29->30... 也就是说，每过 10 个数，十位就会变一次。那么从 1 到 n，十位总共变化了多少次呢？就是 n 里面包含了多少个 10，也就是 floor(n / 10) 次！
百位 (10^2): 同理，百位只在 99->100, 199->200... 的时候变化。从 1 到 n，百位总共变化了 floor(n / 100) 次。
更高位: 我们可以推广这个规律！对于 10^k 这个数位，它在从 1 到 n 的过程中，总共变化了 floor(n / 10^k) 次。

所以，F(n) 的值就是所有数位变化次数的总和！ F(n) = floor(n/1) + floor(n/10) + floor(n/100) + floor(n/1000) + ...F(n) = n + n/10 + n/100 + n/1000 + ... (在程序里用整除就可以啦)

这个公式是不是超级优雅的说！我们只需要一个简单的循环就可以算出 F(n)，然后用 F(r) - F(l) 就能得到最终答案了！

代码实现喵~

cpp

#include <iostream>

// 这个函数用来计算 F(n)，也就是从 1 一直加到 n，总共的数字位变化次数，喵~
//
// 题目要求的是从 l 到 r-1 每次加 1 的变化总和。
// 我们可以用前缀和的思想，把它变成 F(r) - F(l)。
//
// F(n) 的计算公式是基于“贡献法”推导出来的：
// - 个位 (10^0) 的变化次数：每次加1都变，共 n 次。
// - 十位 (10^1) 的变化次数：每逢10变一次，共 floor(n/10) 次。
// - 百位 (10^2) 的变化次数：每逢100变一次，共 floor(n/100) 次。
// - ...
// - 10^k 位的变化次数：共 floor(n/10^k) 次。
//
// 所以 F(n) = n + n/10 + n/100 + ...
// 下面的循环就是这个公式的巧妙实现！
long long F(int n) {
    long long total = 0;
    // 循环计算 n + n/10 + n/100 + ...
    // 每次循环，我们加上当前的 n，然后把 n 除以 10
    // 这就相当于依次加上了 n/1, n/10, n/100 ... 的值
    while (n > 0) {
        total += n;
        n /= 10;
    }
    return total;
}

void solve() {
    int l, r;
    std::cin >> l >> r;
    // 根据我们的推导，从 l 到 r 的总变化数就是 F(r) - F(l)
    std::cout << F(r) - F(l) << "\n";
}

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) 的说。对于每个测试用例，我们调用了两次 F 函数。F(n) 函数中的循环次数取决于 n 的位数，也就是 log10(n)。所以计算 F(r) 和 F(l) 的时间复杂度是 O(log r)。如果有 T 个测试用例，总时间复杂度就是 O(T * log r)，非常快喵！
空间复杂度: O(1) 的说。我们在计算过程中只用了几个变量来存储 l, r 和中间结果，没有使用额外的数组或者数据结构，所以空间消耗是常数级别的。

知识点与总结

这道题虽然标签里有 dp 和 binary search，但最优雅的解法其实是纯数学的，喵~

前缀和/差分思想: 这是解决区间问题的经典利器！将对一个区间 [l, r] 的查询，转化为对两个端点 F(r) 和 F(l) 的查询，大大简化了问题。
贡献法: 当直接模拟或计算很复杂时，可以换个角度，去计算每个基本元素（在这里是每个数位）对总答案的贡献。这种思维方式在很多组合计数和数学题中都非常有用！
优雅的实现: while (n > 0) { total += n; n /= 10; } 这个循环是计算 n + n/10 + n/100 + ... 的一个非常简洁的写法，值得学习和记忆呐！

希望这篇题解能帮助到主人哦！继续加油，享受解题的乐趣吧，喵~ (ฅ'ω'ฅ)

F. Interesting Function - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路大揭秘！ ​

换个角度看问题 ​

如何计算 F(n) 呢？ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结 ​