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

0

datdoo1309 10:50 p.m. 9 Tháng 10, 2023 ← đã chỉnh sửa →

inbox sẽ có code =))
https://www.facebook.com/datdoreal/

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";
    }
}

1 phản hồi

0

chienthancontent 9:22 p.m. 24 Tháng 6, 2023 ← đã chỉnh sửa →

Mn cho mình hỏi code mình như này sao vẫn bị sai đáp án ạ!
https://ideone.com/zkZGlh

-1

sync9w_mk 11:45 p.m. 26 Tháng 5, 2023

test đề bài sai à

1 phản hồi

-1

TrungMegaLikeIT 2:43 p.m. 19 Tháng 5, 2023

Chỉnh lại output đi kìa

-1

nguyentheanh2012 9:27 p.m. 16 Tháng 4, 2023

đề sai

-16

tkminhvolequang 8:19 p.m. 28 Tháng 12, 2022 ← chỉnh sửa 3 →

đề sus

Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.