F Find 3-friendly Integers

本文主要是介绍F Find 3-friendly Integers，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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 333.

For instance:

1.  104{104}104 is 3-friendly because "0" is a substring of "104" and 0mod  3=00 \mod 3 = 00mod3=0.
2.  124{124}124 is 3-friendly because "12" is a substring of "124" and 12mod  3=012 \mod 3 = 012mod3=0. "24" is also a valid substring.
3.  17{17}17 is not 3-friendly because 1mod  3≠0, 7mod  3≠0, 17mod  3≠01 \mod 3 \ne 0, ~7 \mod 3 \ne 0, ~17 \mod 3 \ne 01mod3​=0, 7mod3​=0, 17mod3​=0.

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

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

输入描述:

There are multiple test cases. The first line of the input contains an integer T(1≤T≤10000)T(1 \le T \le 10000)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≤1018)L,R(1 \le L \le R \le 10^{18})L,R(1≤L≤R≤1018), indicating the query.

输出描述:

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

示例1

输入

复制

3
4 10
1 20
1 100

输出

复制

3
11
76

思路：打表题：首先一个结论：若一个数的每一位数字之和为3的倍数，则这个数能被3整除
 其次，我们发现100及以后的数都符合题目所给条件，所以只需要对前100的数进行判断

代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
ll l,r,ans;
vector<int> v;//储存不满足要求的数
int main(){
    for(int i=1;i<10;i++){//一位数
        if(i%3!=0) v.push_back(i);
    }
     for(int i=11;i<100;i++){//两位数
         if(i%10%3!=0&&i/10%3!=0&&i%3!=0){
             v.push_back(i);
         }
     }
    cin>>t;
    while(t--){
        cin>>l>>r;
        ans=r-l+1;//所有的数
        for(int i=0;i<v.size();i++){
            if(v[i]>=l&&v[i]<=r){
                ans--;//减去范围内的不满足要求的数
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

这篇关于F Find 3-friendly Integers的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---