Tổng chữ số

Tác giả:

zipdang04

Dạng bài

Điểm: 1400 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Có \(T\) câu hỏi có dạng: Cho hai số \(a\) và \(b\). Tính tổng toàn bộ các chữ số của các số từ \(a\) tới \(b\).

Hãy trả lời \(T\) câu hỏi trên.

Input

Dòng đầu tiên chứa số \(T\) \((T \leq 10^4)\)
\(T\) dòng sau, mỗi dòng lần lượt chứa 2 số \(a\) và \(b\) \((a, b \le 10^{15})\)

Output

In ra \(T\) dòng lần lượt tương ứng với kết quả của \(T\) câu hỏi trên.

Example

Test 1

Input

2
5 12
12 60

Output

41
378

Bình luận

Mng giúp em với, em dp digit bài này nhưng bị TLE, có cách nào để tối ưu thời gian hơn nữa không ạ, em cảm ơn

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long

vector<int> num;
ll dp[18][163][2];

ll call(int pos, int sum, int f){
    if (pos == num.size()) return sum;
    ll res = dp[pos][sum][f];
    if (res != -1) return res;
    res = 0;
    int LMT = 9;
    if (!f) LMT = num[pos];
    for (int j=0; j<=LMT; j++){
        int nf = f;
        if (j <LMT) nf = 1;
        res += call(pos+1,sum+j,nf);
    }
    return dp[pos][sum][f] = res;
}

ll solve(ll k){
    num.clear();
    while(k>0){
        num.push_back(k%10);
        k /= 10;
    }
    reverse(num.begin(),num.end());
    memset(dp,-1,sizeof(dp));
    return call(0,0,0);
}

main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t; ll l,r;
    cin >> t;
    while(t--){
        cin >> l >> r;
        cout << solve(r) - solve(l-1) << "\n";
    }
}

0

Phatdz123 8:19 p.m. 7 Tháng 3, 2024

ko e :)))))))

6 bình luận nữa