Hướng dẫn giải của Giải phương trình 2
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu tìm số nguyên dương x nhỏ nhất sao cho phương trình x^2 + S(x) * x - N = 0 được thỏa mãn, trong đó S(x) là tổng các chữ số của x. N là số nguyên dương cho trước, có thể lên tới 10^18. Nếu không có nghiệm thì in ra -1.
Các cách tiếp cận
Cách Brute Force (Duyệt x)
#include <iostream>
#include <cmath>
using namespace std;
long long sumDigits(long long x) {
long long s = 0;
while (x) {
s += x % 10;
x /= 10;
}
return s;
}
int main() {
long long N;
cin >> N;
for (long long x = 1; ; x++) {
if (x * x + x * sumDigits(x) == N) {
cout << x;
return 0;
}
if (x * x > N) break; // Tối ưu: nếu x^2 đã lớn hơn N thì dừng
}
cout << -1;
return 0;
}
- Time Complexity: O(√N * log N)
- Space Complexity: O(1)
Phương trình x^2 + S(x)x = N suy ra x^2 <= N, do S(x) >= 0. Do đó x <= √N. Ta có thể duyệt x từ 1 đến √N. Với mỗi x, tính S(x) và kiểm tra. Độ phức tạp là O(√N) vòng lặp, mỗi vòng lặp tốn O(log x) để tính tổng chữ số. Với N = 10^18, √N = 10^9, cách này quá chậm.
Cách Duyệt theo tổng chữ số S(x)
#include <iostream>
#include <cmath>
#include <algorithm>
#include <climits>
using namespace std;
long long sumDigits(long long x) {
long long s = 0;
while (x) {
s += x % 10;
x /= 10;
}
return s;
}
int main() {
long long N;
cin >> N;
long long ans = -1;
// S(x) la tong chu so cua x.
// Do x <= sqrt(N) <= 10^9, S(x) co the la toi da 9 * 10 = 90.
// Nhung de an toan hon, ta co the chon nguong 162 (9 * 18).
for (int S = 1; S <= 162; ++S) {
// Giai phuong trinh x^2 + Sx - N = 0
// Cong thuc: x = (-S + sqrt(S^2 + 4N)) / 2
// Ta can x la so nguyen duong.
// Tinh delta
long double delta = (long double)S * S + 4.0L * N;
long double sq = sqrtl(delta);
// Tinh x gan dung
long long x = (long long)((-S + sq) / 2);
// Kiem tra xung quanh x de chong sai so
for (long long t = max(1LL, x - 2); t <= x + 2; ++t) {
if (t > 0 && t * t + t * sumDigits(t) == N) {
if (ans == -1 || t < ans) ans = t;
}
}
}
cout << ans;
return 0;
}
- Time Complexity: O(162 * log N)
- Space Complexity: O(1)
Từ phương trình x^2 + S(x)x = N, ta thấy x xấp xỉ √N. Tổng chữ số S(x) của x rất nhỏ so với x (S(x) <= 9 * log10(x)). Ta có thể ẩn S(x) và coi nó là một biến S chạy từ 1 đến một giá trị nhỏ (ví dụ 162). Với mỗi giá trị S, phương trình trở thành x^2 + Sx - N = 0. Ta có thể giải nghiệm x bằng công thức nghiệm. Do S(x) thực tế chỉ bằng S khi x là nghiệm, ta duyệt một khoảng nhỏ xung quanh nghiệm tìm được để kiểm tra lại. Độ phức tạp O(162) rất nhanh.
Cách Duyệt xung quanh căn bậc hai của N
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
long long sumDigits(long long x) {
long long s = 0;
while (x > 0) {
s += x % 10;
x /= 10;
}
return s;
}
int main() {
long long N;
cin >> N;
// x^2 + S(x)x = N => x(x + S(x)) = N
// x approx sqrt(N)
long long k = sqrtl(N);
long long ans = -1;
// Ta can x sao cho x^2 <= N.
// S(x) la toi da 9 * 18 = 162.
// Khoang cach tu x den sqrt(N) la rat nho.
// Ta chi can xet x quanh sqrt(N).
for (long long x = max(1LL, k - 200); x <= k + 200; x++) {
if (x * x + x * sumDigits(x) == N) {
ans = x;
break; // Tim x nho nhat nen gap la dung
}
}
cout << ans;
return 0;
}
- Time Complexity: O(400 * log N) ~ O(1)
- Space Complexity: O(1)
Đây là cách tiếp cận trực quan nhất. Từ phương trình x^2 + S(x)x = N, ta có x(x + S(x)) = N. Vì S(x) > 0, nên x < √N. Xấp xỉ x = √N. Sai lệch giữa x và √N do hệ số S(x) là rất nhỏ (vì S(x) chỉ có thể lớn nhất là 162). Do đó, x phải nằm trong một khoảng rất hẹp xung quanh √N. Duyệt từ max(1, √N - 200) đến √N + 200 là đủ để tìm ra nghiệm (nếu có). Đây là cách hiệu quả và dễ code nhất.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(√N * log N) | O(1) | Brute Force (Duyệt x) |
| 2 | O(162 * log N) | O(1) | Duyệt theo tổng chữ số S(x) |
| 3 | O(400 * log N) ~ O(1) | O(1) | Duyệt xung quanh căn bậc hai của N |
Bài học kinh nghiệm
- Phương trình x^2 + S(x)x = N suy ra x^2 <= N, do đó x <= sqrt(N). Điều này giảm đáng kể không gian tìm kiếm.
- Tổng chữ số S(x) là một hàm tăng rất chậm, có giá trị tối đa nhỏ (khoảng 162 cho N <= 10^18). Do đó, x gần như là nghiệm của phương trình x^2 + Sx - N = 0 với S cố định.
- Nghiệm x phải nằm rất gần giá trị sqrt(N).
Lỗi thường gặp
- Sử dụng biến số nguyên để tính toán công thức nghiệm có thể gây tràn số (overflow). Nên dùng số thực có độ chính xác cao (long double) hoặc tính toán cẩn thận.
- Quên kiểm tra các số x xung quanh nghiệm tìm được để xử lý sai số làm tròn khi tính sqrt.
- Nếu duyệt theo S, cần đảm bảo giới hạn S đủ lớn (ví dụ 162 hoặc 200) để bao quát tất cả trường hợp.
Bình luận