题目内容

多乡的家乡最近推出了一种新型彩票，规则非常有趣，如果一个数字中，隐藏着一个连续的子串，且这个子中代表的数是$3$的倍数。那么这个数字就是“幸运数字"。彩票每期都会公布一个范围$[L,R]$。并从这个范围的“幸运数字”中随机选择一个作为中奖号码，

以下是一些例子，辅助理解“幸运数字”的含义:

题解

题目描述

多多的家乡推出了一种新型彩票，规则是：如果一个数字中存在一个连续子串（去除前导零后的数值）是3的倍数，则该数字为“幸运数字”。给定范围$[L, R]$，求其中幸运数字的个数。

思路分析

这道题的核心思路是通过观察发现，任何位数≥3的数字必定包含一个子串是3的倍数，因此都是“幸运数字”。对于1位数和2位数，需要单独判断是否满足条件。预处理所有符合条件的2位数，并利用二分查找快速统计范围内的非幸运数字数目。最终，用总数减去非幸运数字的数目，即可得到幸运数字的个数。