2021牛客暑期多校训练营1 F题 Find 3-friendly Integers

A positive integer is 3-friendly if and only if we can find a continuous substring in its decimal representation, and the decimal integer represented by the substring is a multiple of $3$.

For instance:

1. ${104}$ is 3-friendly because "0" is a substring of "104" and 0mod   $0\mod3=0$.
2. ${124}$ is 3-friendly because "12" is a substring of "124" and $12\mod3=0$ . "24" is also a valid substring.
3. ${17}$ is not 3-friendly because $1\mod  3≠0, 7\mod  3≠0, 17\mod  3≠0$ .

Note that the substring with leading zeros is also considered legal.

Given two integers ${L}$ and ${R}$ , you are asked to tell the number of positive integers ${x}$ such that $L≤x≤R$ and ${x}$ is 3-friendly.

输入描述:

There are multiple test cases. The first line of the input contains an integer $T(1 \le T \le 10000)$ , indicating the number of test cases. For each test case:

The only line contains two integers $L,R(1 \le L \le R \le 10^{18})$, indicating the query.

输出描述:

For each test case output one line containing an integer, indicating the number of valid ${x}$ .

示例1

输入

3
4 10
1 20
1 100

输出

3
11
76

题解

这道题是一道规律题（呜呜一开始看成了数位dp，被自己蠢到），问你 $l-r$ 之间有多少个数满足至少有一个字串是3的倍数（注意0也是）。

核心规律就是：

1. 当数字大于100时，所有数一定满足条件（任意三个10以内数字，一定满足数字之间有某种相加方式得到的结果是3的倍数）。
2. 100以内，打表或者暴力判断均可。

这道题可以打一个表看看规律，也可以直接推理得到（去推数位dp的我是真的傻）。

代码

代码如下：

#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
const int maxn = 2e3 + 10;
typedef long long ll;

int T;
ll l, r;
int a[100] = {
    1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1,
    0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1,
    1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0,
    1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
};

int main() { 
  cin >> T;
  while (T--) {
    cin >> l >> r;
    ll sum = 0;
    if (l >= 100) {
      sum = r - l + 1;
    } else {
      if (r < 100) {
        for (int i = l; i <= r; i++) {
          if (a[i]) sum++;
        }
      } else {
        sum += r - 100 + 1;
        for (int i = l; i <= 99; i++) {
          if (a[i]) sum++;
        }
      }
    }
    cout << sum << endl;
  }
  return 0;
}