CF_725_F
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051
// Problem: F. Interesting Function
// Contest: Codeforces - Codeforces Round #725 (Div. 3)
// URL: https://codeforces.com/contest/1538/problem/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include "bits/stdc++.h"
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
using ll = long long;
ll dp[10] ;
void generateDP(){
ll t[10] ;
t[0] = dp[0] = 1 ;
ll sum = 11 ;
t[1] = 10 ;
for(ll i = 2 ; i< 10 ; i++){
t[i] = (9*(sum)+1) ;
sum += t[i] ;
}
for(int i = 1; i < 10 ;i++ ){
dp[i] = dp[i-1] + t[i] ;
}
}
ll getTillN(string s){
ll len = s.size() ;
ll retVal = 0;
len--;
for(ll i = 0 ; i < (ll)s.size() ; i++ ){
retVal += dp[len]*(s[i]-'0') ;
}
return retVal ;
}
ll solve(ll l , ll r ){
return getTillN(to_string(r) ) - getTillN(to_string(l)) ;
}
int main(){
FIO
ll t ; cin >> t ;
generateDP() ;
while(t--){
ll l , r ; cin >> l >> r ;
cout << solve(l,r) <<"\n" ;
}
return 0 ;
}
Cpp
INFO