Hướng dẫn giải của [200 đề thầy Đức] Bài 49: Tổng dịch trái
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Với N và k, tổng cần tìm là N + N·10 + N·10^2 + ... + N·10^k = N·(1 + 10 + ... + 10^k). Ví dụ N = 12, k = 3: 12 + 120 + 1200 + 12000 = 13332.
Sub 1: Cộng dồn từng số hạng — ~O(k)~
Giữ giá trị hiện tại val = N, mỗi vòng nhân val với 10 rồi cộng vào tổng. Đạt 16/16 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n, k;
cin >> n >> k;
// Cộng dồn: giá trị N, N*10, N*10^2, ..., N*10^k
long long total = n, val = n;
for (int i = 1; i <= k; i++) {
val *= 10; // dịch trái thêm một lần
total += val;
}
cout << total << "\n";
return 0;
}
Sub 2: Công thức — ~O(k)~
Tổng là N nhân với số gồm k + 1 chữ số 1 (1 + 10 + ... + 10^k). Vòng lặp tính số này, sau đó nhân với N. Kết quả lớn nhất khoảng 10^4 · 1.1·10^10 nên dùng long long. Đạt 16/16 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n, k;
cin >> n >> k;
// Tổng = N * (1 + 10 + ... + 10^k) = N * (10^(k+1) - 1) / 9
long long rep = 0, p = 1; // rep = 1 + 10 + ... + 10^k
for (int i = 0; i <= k; i++) {
rep += p;
p *= 10;
}
cout << n * rep << "\n";
return 0;
}
Bình luận