Find 3-friendly Integers

Find 3-friendly Integers

链接：https://ac.nowcoder.com/acm/contest/11166/F
来源：牛客网

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:
104 is 3-friendly because “0” is a substring of “104” and 0mod3=0.

124 is 3-friendly because “12” is a substring of “124” and 12mod3=0. “24” is also a valid substring.

17 is not 3-friendly

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 R(L≤x≤R) and x is 3-friendly.
输入描述:
There are multiple test cases. The first line of the input contains an integer T(1≤T≤10000), indicating the number of test cases. For each test case:

The only line contains two integers L,R(1≤L≤R≤10^18 ), indicating the query.

输出描述:
For each test case output one line containing an integer, indicating the number of valid {x}x.
思路:
其实就是算出前100个,100以后的数都是3的友好型

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll sum[105];
ll a(ll x)
{
    
    if(x<=99)
        return sum[x];
    if(x>99)
    {
    
        return sum[99]+x-99;
    }
}
int main()
{
    
    for(int i=1;i<=9;i++)
    {
    
        ll cc=0;
        if(i%3==0)
            cc=1;
        sum[i]=sum[i-1]+cc;
    }
    for(int i=10;i<=99;i++)
    {
    
        ll cc=0;
        if(i%3==0)
        {
    
            cc=1;
        }
        if(i/10%3==0)
        {
    
            cc=1;
        }
        if(i%10%3==0)
        {
    
            cc=1;
        }
        sum[i]=sum[i-1]+cc;
    }
    int T;
    cin>>T;
    while(T--)
    {
    
        ll l,r;
        cin>>l>>r;
        cout<<a(r)-a(l-1)<<endl;
    }
    return 0;
}