Submission

Score: 10

User: GastrointestinalTrackInflammation

Problemset: Croissaria Number

Language: cpp

Time: 0.239 second

Submitted On: 2026-10-06 11:37:48

#include<bits/stdc++.h>

using namespace std;

#define inall(x) for(auto& i:x)cin>>i;
#define outall(x) {for(auto i:x)cout<<i<<' ';cout<<endl;}
#define ini(x,y) for(auto& i:x)i=y;
#define tout(x) cout<<"DEBUG! :"<<x<<endl;
#define rout(x) {cout<<x<<endl;return;}
using ll = long long;
using df = double;

template<typename pair1,typename pair2>
istream& operator>>(istream& in,pair<pair1,pair2>&p) {return in>>p.first>>p.second;}

template <typename pair1, typename pair2>
ostream& operator<<(ostream& out,const pair<pair1,pair2>&p) {return out<<endl<<p.first<<' '<< p.second;}

ll precom[19][10];

int oom(ll n){
    int ans=0;
    while(n>=10){
        ans++;
        n/=10;
    }
    return ans;
}

ll findlimit(ll l,ll n){
    if(n==0)return 1;
    vector<ll>vec,pvec;
    while(n>0){
        ll cur=n%10;
        vec.push_back(cur);
        ll prev=1;
        if(!pvec.empty())prev=pvec.back();
        pvec.push_back(prev*min(l,cur+1));
        n/=10;
    }
    ll ans=0;
    for(int i=0;i<vec.size();i++){
        ll prev=1;
        if(i!=0)prev=pvec[i-1];
        if(i==0){
            ans+=min(l,vec[i])*prev;
        }else{
            ans+=min(l-1,max((ll)0,vec[i]-1))*prev;
        }
    }
    return ans;
}

ll cnumber(ll n){
    if(n<=9)return 0;
    int i=oom(n);
    ll p10=(ll)pow(10,i);
    ll ans=0;
    for(int j=0;j<n/p10;j++){
        ans+=precom[i][j];
    }
    ans+=findlimit(n/p10,n%p10);
    //cout<<n<<' '<<ans<<endl;
    return ans;
}

void solve(){
    ll l,r;
    cin>>l>>r;
    cout<<cnumber(r)-cnumber(l-1)<<endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    for(int j=0;j<=9;j++)precom[0][j]=0;
    for(int i=1;i<=18;i++){
        precom[i][0]=0;
        for(int j=1;j<=9;j++)precom[i][j]=(ll)pow(j,i);
        for(int j=0;j<=9;j++)precom[i][0]+=precom[i-1][j];
    }
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}