洛谷P4942 小凯的数字 学习笔记

今天做了一道赏心悦目的数学题：https://www.luogu.com.cn/problem/P4942

用了3种方法，反复学习大佬的思路，优化优化再优化，终于A了。

题目描述：

小凯有一天突发奇想，写下了一串数字：

例如：时，数字为：

           时数字为：

小凯很喜欢数字 9，所以他想问你他写下的数字除以 9 的余数是多少

例如：时，

输入格式：

第一行为数字 Q,表示小凯有 Q 个问题

第 2 到 Q+1 行，每行两个数字 l,r 表示数字范围

输出格式:

对于每行的问题输出一行，一个数字，表示小凯问题的回答

看了半天先把题看错了。我和某罗一直以为是  

打了半天发现样例都没过，才知道是把题看错了。。。

原来是要把这些数字组合成一个大数字，从前往后写就是，然后就没辙了。

思来想去，想到如果一个数是$9$的倍数，那么它的个位数字之和也是9的倍数，既是：

于是有了这样的代码：

就是从l到r枚举，然后拆分数字取模，显然会超时，只有60分。

看着大佬的题解，又有了一个新的思路，我们可以把上式颠倒一下，也能成立。举个例子：

若一个数是由多个数拼成的，那就不需要再把原数二次拆开，直接把原数加起来模$9$就行了。于是有了进阶版：

也超时了。那看来只能用一种能摆脱大循环的方法了。

有了这个式子：

对于每个数p ,显然都有任意整数 n 满足：

这个式子左边可以写成:

其中有p个n，那就可以写成：

显然，这是p的倍数。

那在这个区间，即l到r中，一定有这个式子所覆盖的数，那这些数我们就可以不用管了。

只需要计算这些数之外的数

到思考的最后一步，我们可以让l和r分别模9，相减计数后输出即可。

结束。

题解参考地址:https://www.luogu.com.cn/blog/ttjb/solution-p4942