#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
ll dp[20][200],dp2[20][200][2],il[N];
ll sum(ll a){
string s="";
while(a>0){
s+=char((a%10)+48);
a/=10;
}
reverse(s.begin(),s.end());
dp[0][0]=1;
for(int i=1;i<s.size();i++){
for(int sum=(i==1);sum<=i*9;sum++){
dp[i][sum]=0;
for(int j=(i==1);j<=min(9,sum);j++) dp[i][sum]+=dp[i-1][sum-j];
}
}
dp2[0][0][0]=1;
for(int i=1;i<=s.size();i++){
for(int sum=(i==1);sum<=i*9;sum++){
int curr=int(s[i-1])-48;
dp2[i][sum][1]=0;
for(int j=(i==1);j<=min(sum,9);j++){
dp2[i][sum][1]+=dp2[i-1][sum-j][1];
if(j<curr) dp2[i][sum][1]+=dp2[i-1][sum-j][0];
}
if(curr<=sum) dp2[i][sum][0]=dp2[i-1][sum-curr][0];
else dp2[i][sum][0]=0;
}
}
for(int i=1;i<s.size();i++)
for(int j=0;j<=190;j++) il[j]+=dp[i][j];
for(int i=0;i<=190;i++) il[i]+=dp2[s.size()][i][0]+dp2[s.size()][i][1];
ll res=0;
for(int i=0;i<=190;i++){
int curr=i,pop=-1;
while(curr!=pop){
int curr2=curr,aktsum=0;
while(curr2>0){
aktsum+=curr2%10;
curr2/=10;
}
pop=curr;
curr=aktsum;
}
res+=il[i]*(ll)curr;
il[i]=0;
}
return res;
}
void solve(){
ll a,b;
cin>>a>>b;
cout<<sum(b)-sum(a-1)<<"\n";
}
int main(){
ios_base::sync_with_stdio(0),cin.tie(0);
int tt=1;
cin>>tt;
while(tt--) solve();
}
Compilation message
trol.cpp: In function 'll sum(ll)':
trol.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for(int i=1;i<s.size();i++){
| ~^~~~~~~~~
trol.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for(int i=1;i<=s.size();i++){
| ~^~~~~~~~~~
trol.cpp:48:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int i=1;i<s.size();i++)
| ~^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Correct |
9 ms |
340 KB |
Output is correct |
| 4 |
Correct |
3 ms |
380 KB |
Output is correct |
| 5 |
Correct |
10 ms |
432 KB |
Output is correct |
