Hướng dẫn giải của Số chia hết (đề Vĩnh Phúc 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
Dãy cần tìm gồm các số nguyên dương x mà tổng chữ số của x chia hết cho số chữ số của x. Cần tìm số thứ K trong dãy với K ≤ 10^5. Đáp án nhỏ (cỡ vài triệu), nên duyệt lần lượt các số và đếm là đủ nhanh.
Sub 1: Vét cạn — ~O(X \cdot d)~
Xét lần lượt x = 1, 2, 3, .... Với mỗi x, đổi sang chuỗi để tính tổng chữ số và số chữ số, nếu tổng chia hết cho số chữ số thì tăng bộ đếm. Khi bộ đếm bằng K thì in x. Ở đây X là đáp án và d là số chữ số, d ≤ 7.
Kết quả chấm: đạt 24/24 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("DIVN.INP", "r")) { freopen("DIVN.INP", "r", stdin); freopen("DIVN.OUT", "w", stdout); }
long long k;
cin >> k;
// Vet can: xet lan luot cac so nguyen duong 1, 2, 3, ...
// Voi moi so, tach chu so bang chuoi, tinh tong chu so va so chu so,
// neu tong chia het cho so chu so thi dem; den so thu k thi in ra
long long cnt = 0;
for (long long x = 1;; x++) {
string s = to_string(x);
long long sum = 0;
for (char c : s) sum += c - '0';
if (sum % (long long)s.size() == 0) {
cnt++;
if (cnt == k) {
cout << x << "\n";
return 0;
}
}
}
return 0;
}
Sub 2: Tách chữ số bằng phép chia — ~O(X \cdot d)~
Cách làm giống sub 1 nhưng không đổi sang chuỗi: lấy t % 10 để cộng vào tổng và đếm số chữ số bằng t /= 10. Phép toán số học nhanh hơn việc tạo chuỗi nên chạy nhanh hơn một chút. Bài này không có cách nào tốt hơn đáng kể, vì đáp án đã nhỏ nên vét cạn vẫn qua hết test.
Kết quả chấm: đạt 24/24 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("DIVN.INP", "r")) { freopen("DIVN.INP", "r", stdin); freopen("DIVN.OUT", "w", stdout); }
long long k;
cin >> k;
// Dem cac so thoa man: tong chu so chia het cho so chu so.
// Khong can chuyen sang chuoi: tach chu so bang phep chia 10 va dem so chu so luon.
long long cnt = 0;
for (long long x = 1;; x++) {
long long t = x, sum = 0;
int digits = 0;
while (t > 0) {
sum += t % 10;
t /= 10;
digits++;
}
if (sum % digits == 0) {
cnt++;
if (cnt == k) {
cout << x << "\n";
return 0;
}
}
}
return 0;
}
Bình luận