Hướng dẫn giải của [200 đề thầy Đức] Bài 61: Giải phương trình
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
Tìm số nguyên dương ~x \le 10^8~ nhỏ nhất thoả ~S(x) \cdot x = a~, với ~S(x)~ là tổng chữ số của ~x~.
Sub 1: Thử lần lượt từng x — ~O(\min(a, 10^8) \cdot \log)~, dùng khi ~a \le 10^6~
Thử ~x = 1, 2, \dots~ đến ~\min(a, 10^8)~, gặp ~x~ đầu tiên có ~S(x) \cdot x = a~ thì in ra. Không có thì in -1.
Nếu chỉ nộp sub này: đúng 12/19 test.
Sub 2: Duyệt ước của a — ~O(\sqrt{a} \cdot \log)~, dùng khi mọi trường hợp còn lại
Vì ~S(x) \ge 1~ nên ~x~ chia hết ~a~ và ~x \le a~. Chỉ cần duyệt các ước của ~a~ (qua căn bậc hai, lấy cả ~i~ và ~a/i~), kiểm tra điều kiện rồi lấy ~x~ nhỏ nhất.
Nếu chỉ nộp sub này: đúng 19/19 test.
Chương trình hoàn chỉnh
Chương trình đọc ~a~. Nếu ~a \le 10^6~ thì gọi sub1, ngược lại gọi sub2. Nếu không có nghiệm thì in -1.
#include <bits/stdc++.h>
using namespace std;
long long a; // gia tri a cua phuong trinh S(x) * x - a = 0
long long digitSum(long long x) {
long long s = 0;
while (x > 0) {
s += x % 10;
x /= 10;
}
return s;
}
// Sub 1: vet can. Thu x = 1, 2, ... (x <= min(a, 10^8)), gap x dau tien thoa S(x) * x = a.
// Dung khi a <= 10^6.
void sub1() {
long long lim = min(a, 100000000LL);
for (long long x = 1; x <= lim; x++)
if (digitSum(x) * x == a) {
cout << x << "\n";
return;
}
cout << -1 << "\n";
}
// Sub 2: neu S(x) * x = a thi x chia het a, nen chi can thu cac uoc cua a.
// Duyet uoc qua can bac hai, lay x nho nhat thoa man (x <= 10^8). O(sqrt(a) * log).
void sub2() {
long long best = -1;
for (long long i = 1; i * i <= a; i++) {
if (a % i != 0) continue;
long long cand[2] = {i, a / i};
for (long long x : cand)
if (x <= 100000000LL && digitSum(x) * x == a)
if (best == -1 || x < best) best = x;
}
cout << best << "\n";
}
int main() {
cin >> a;
if (a <= 1000000) sub1();
else sub2();
return 0;
}
Bình luận