Find 3-friendly Integers

题目描述

求范围\([L,R]\)内有多少个数满足数的子串是3的倍数

范围

\([L,R] \leq 10^{18}\)

题解

\(n \geq 100\)一定合法，暴力算即可

代码

#include
#include
using namespace std;
#define ll long long
ll f(ll n){
    ll ans=0;
    for(ll i=1;i<=min(n,99ll);++i){
        ll x=i,sum=0;
        bool f=0;
        while(x){
            sum+=x%10;
            if(x%10%3==0) f=1;
            if(sum%3==0) f=1;
            x/=10;
        }
        if(f) ++ans;
    }
    if(n>=100) ans+=n-99;
    return ans;
}
int main(){
    int T; scanf("%d",&T); while(T--){
        ll L,R;
        scanf("%lld %lld",&L,&R);
        printf("%lld\n",f(R)-f(L-1));
    }
}