Hướng dẫn giải của [200 đề thầy Đức] Bài 21: Số hoàn hảo thứ k
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ố nguyên dương hoàn hảo là số có tổng các chữ số bằng 10. Cần tìm số thứ K trong dãy các số như vậy (K \le 10^4).
Sub 1: Vét cạn — ~O(X \cdot \log X)~
Duyệt x = 1, 2, 3, ..., tính tổng chữ số, đếm các số có tổng bằng 10 cho đến khi đếm đủ K. Đạt 35/35 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long K;
cin >> K;
long long cnt = 0;
// Vét cạn: duyệt lần lượt các số nguyên dương x = 1, 2, ..., tính tổng chữ số
for (long long x = 1;; x++) {
long long s = 0, y = x;
while (y > 0) {
s += y % 10;
y /= 10;
}
if (s == 10 && ++cnt == K) {
cout << x << "\n";
return 0;
}
}
}
Sub 2: Bước nhảy theo modulo 9 — ~O(X \cdot \log X / 9)~
Tổng chữ số của x đồng dư với x modulo 9. Nếu tổng chữ số bằng 10 thì x \equiv 1 \pmod 9, nên chỉ cần duyệt x = 1, 10, 19, ... (bước 9). Đạt 35/35 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long K;
cin >> K;
long long cnt = 0;
// Tổng chữ số của x đồng dư với x modulo 9, nên tổng chữ số = 10 thì x ≡ 1 (mod 9).
// Chỉ cần duyệt x = 1, 10, 19, ... (bước nhảy 9) và kiểm tra tổng chữ số.
for (long long x = 1;; x += 9) {
long long s = 0, y = x;
while (y > 0) {
s += y % 10;
y /= 10;
}
if (s == 10 && ++cnt == K) {
cout << x << "\n";
return 0;
}
}
}
Bình luận