Tổng chữ số

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

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

1

ttsang 9:16 p.m. 31 Tháng 8, 2024

bn dùng c++20 nhé:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
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);
}
int 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

pesekowen 11:41 p.m. 19 Tháng 8, 2024 ← chỉnh sửa 3 →

bạn chuyển cái memset dp vào trong hàm main đi bạn

1

Đăng_Khoa 10:24 a.m. 14 Tháng 6, 2024

dùng c++20 đi bạn

0

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

ko e :)))))))

6 bình luận nữa