题解

题目描述

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

思路分析

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

1. 关键观察：

   • 任何位数≥3的数字必定包含一个子串和为3的倍数，因此都是幸运数字。
   • 只需考虑1位和2位的数字是否非幸运。

2. 非幸运数字条件：

   • 1位数：该数本身不能被3整除。
   • 2位数：十位和个位均不能被3整除，且它们的和也不能被3整除。

3. 解决步骤：

   • 预处理所有符合条件的2位数。
   • 对每个查询，统计区间内的非幸运数字数目，总数减去非幸运数即为答案。

C++ 代码

#include <bits/stdc++.h>
using namespace std;

vector<int> valid;

void preprocess() {
    vector<int> d1_list = {1, 2, 4, 5, 7, 8};
    vector<int> d2_list = {1, 2, 4, 5, 7, 8};
    for (int d1 : d1_list) {
        for (int d2 : d2_list) {
            if ((d1 % 3) == (d2 % 3)) {
                valid.push_back(d1 * 10 + d2);
            }
        }
    }
    sort(valid.begin(), valid.end());
}

int main() {
    preprocess();
    int T;
    scanf("%d", &T);
    while (T--) {
        long long L, R;
        scanf("%lld%lld", &L, &R);
        long long total = R - L + 1;
        // 计算1位数中的非幸运数目
        long long count_1 = 0;
        long long start_1 = max(L, 1LL);
        long long end_1 = min(R, 9LL);
        if (start_1 <= end_1) {
            long long total_1 = end_1 - start_1 + 1;
            long long cnt_div3 = (end_1 / 3) - ((start_1 - 1) / 3);
            count_1 = total_1 - cnt_div3;
        }
        // 计算2位数中的非幸运数目
        long long count_2 = 0;
        long long left = max(L, 10LL);
        long long right = min(R, 99LL);
        if (left <= right) {
            auto l = lower_bound(valid.begin(), valid.end(), left);
            auto r = upper_bound(valid.begin(), valid.end(), right);
            count_2 = r - l;
        }
        // 结果
        long long ans = total - (count_1 + count_2);
        printf("%lld\n", ans);
    }
    return 0;
}

Python 代码

import bisect

valid = []
for d1 in [1, 2, 4, 5, 7, 8]:
    for d2 in [1, 2, 4, 5, 7, 8]:
        if d1 % 3 == d2 % 3:
            valid.append(d1 * 10 + d2)
valid.sort()

T = int(input())
for _ in range(T):
    L, R = map(int, input().split())
    total = R - L + 1
    # 处理1位数
    count_1 = 0
    start_1 = max(L, 1)
    end_1 = min(R, 9)
    if start_1 <= end_1:
        total_1 = end_1 - start_1 + 1
        cnt_div3 = (end_1 // 3) - ((start_1 - 1) // 3)
        count_1 = total_1 - cnt_div3
    # 处理2位数
    count_2 = 0
    left = max(L, 10)
    right = min(R, 99)
    if left <= right:
        l = bisect.bisect_left(valid, left)
        r = bisect.bisect_right(valid, right)
        count_2 = r - l
    # 结果
    ans = total - (count_1 + count_2)
    print(ans)

Java

import java.util.*;

public class Main {
    static List<Integer> valid = new ArrayList<>();

    static void preprocess() {
        int[] d1List = {1, 2, 4, 5, 7, 8};
        int[] d2List = {1, 2, 4, 5, 7, 8};
        for (int d1 : d1List) {
            for (int d2 : d2List) {
                if (d1 % 3 == d2 % 3) {
                    valid.add(d1 * 10 + d2);
                }
            }
        }
        Collections.sort(valid);
    }

    public static void main(String[] args) {
        preprocess();
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        while (T-- > 0) {
            long L = scanner.nextLong();
            long R = scanner.nextLong();
            long total = R - L + 1;
            // 处理1位数
            long count_1 = 0;
            long start_1 = Math.max(L, 1);
            long end_1 = Math.min(R, 9);
            if (start_1 <= end_1) {
                long total_1 = end_1 - start_1 + 1;
                long cnt_div3 = (end_1 / 3) - ((start_1 - 1) / 3);
                count_1 = total_1 - cnt_div3;
            }
            // 处理2位数
            long count_2 = 0;
            long left = Math.max(L, 10);
            long right = Math.min(R, 99);
            if (left <= right) {
                int l = Collections.binarySearch(valid, (int) left);
                if (l < 0) l = -l - 1;
                int r = Collections.binarySearch(valid, (int) right + 1);
                if (r < 0) r = -r - 1;
                count_2 = r - l;
            }
            // 结果
            long ans = total - (count_1 + count_2);
            System.out.println(ans);
        }
    }
}

题目内容

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

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

$1.107$是“幸运数字":$0$是$107$的子串，且$0$是$3$的倍数

$2.25$不是“幸运数字":$25$有$3$个子串分别是$2、5、25$，它们都不是3的倍数

$3.2521$是"幸运数字":$21$是$2521$的子串，且$21$是$3$的倍数

注意子串必须是连续的，例:在数字$152$中，$15$是子串，$12$不是子串

以$0$开头的子串需要抹去先导$0$来考虑数值，例:在数字$103$中，$03$是一个子串，它的值为$3$，也是$3$的倍数

多多想知道$[L,R]$中有多少个幸运数字，你能帮帮他吗

输入描述

有多个测试用例。输入的第一行包含一个整数$T(1<=T<=10000)$，表示测试用例的数量;

每组输入仅一行，包含两个整数$L,R(1<=L<=R<=1e18)$

输出描述

对每个测试用例，输出一个整表示区间$[L,R]$中“幸运数字"的个数

样例1

输入

2
8 19
2 45

输出

8
31