Hướng dẫn giải của Bài toán phép nhân Nga (đề Trà Vinh 2021)
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
Đề yêu cầu nhập hai số nguyên dương a, b và tính tích a·b bằng thuật toán nhân Nga: lập cột nhân đôi (a, 2a, 4a, ...) và cột chia đôi (b, ⌊b/2⌋, ..., 1), rồi cộng các giá trị ở cột nhân đôi ứng với những dòng có số lẻ ở cột chia đôi.
Sub 1: Cộng a đúng b lần — ~O(b)~
Đây là cách nhân trực tiếp theo định nghĩa: cộng a vào kết quả b lần. Đúng nhưng với b lớn thì chậm.
Kết quả chấm: đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long a, b;
cin >> a >> b;
// Vét cạn: cộng a vào kết quả đúng b lần (chậm khi b lớn)
long long tich = 0;
for (long long i = 0; i < b; i++)
tich += a;
cout << tich << "\n";
return 0;
}
Sub 2: Thuật toán nhân Nga — ~O(\log b)~
Lặp khi b > 0: nếu b lẻ thì cộng a vào kết quả; sau đó nhân đôi a và chia đôi b (lấy phần nguyên). Số vòng lặp chỉ bằng số chữ số nhị phân của b.
Bẫy: tích có thể lớn hơn a và b, nên dùng long long.
Kết quả chấm: đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long a, b;
cin >> a >> b;
// Phép nhân Nga: cột nhân đôi (a, 2a, ...) và cột chia đôi (b, b/2, ..., 1)
// Cộng các giá trị ở cột nhân đôi tương ứng với dòng có cột chia đôi là số lẻ
long long tich = 0;
while (b > 0) {
if (b % 2 == 1) tich += a; // dòng có số lẻ ở cột chia đôi thì cộng giá trị nhân đôi
a *= 2; // cột nhân đôi
b /= 2; // cột chia đôi
}
cout << tich << "\n";
return 0;
}
Bình luận