Hướng dẫn giải của LOOP26: Nén số
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
Số nén tối giản là kết quả của việc lặp "tính tổng các chữ số" cho đến khi còn một chữ số. Với N ≤ 10^9 có thể mô phỏng trực tiếp.
Sub 1: Mô phỏng phép nén — ~O(log^2 N)~
Lặp: nếu N còn từ hai chữ số trở lên thì thay N bằng tổng chữ số của N. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n;
cin >> n;
// Lặp việc tính tổng các chữ số cho đến khi chỉ còn một chữ số
while (n >= 10) {
long long s = 0;
while (n > 0) {
s += n % 10;
n /= 10;
}
n = s;
}
cout << n << "\n";
return 0;
}
Sub 2: Công thức gốc số — ~O(1)~
Tổng chữ số của một số đồng dư với chính nó modulo 9, nên số nén tối giản là 1 + (N − 1) mod 9 với N ≥ 1 (đây là "gốc số" của N). Lưu ý dùng số nguyên dương N nên không cần xử lý trường hợp 0. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n;
cin >> n;
// Với N >= 1, kết quả là "gốc số" (digital root): 1 + (N - 1) mod 9
// Phép nén lặp lại đúng bằng số dư modulo 9, không cần tính tổng nhiều lần
cout << 1 + (n - 1) % 9 << "\n";
return 0;
}
Bình luận