Hướng dẫn giải của LOOP27: Phân tích 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
Với số nguyên dương ~N~, tìm hai số nguyên dương ~x \le y~ sao cho ~xy = N~ và ~x + y~ nhỏ nhất.
Sub 1: Duyệt tất cả ước — ~O(N)~, dùng khi ~N \le 10^6~
Duyệt ~x~ từ 1 đến ~N~, nếu ~x~ là ước của ~N~ và ~x \le N/x~ thì xét cặp ~(x, N/x)~ và cập nhật cặp có tổng nhỏ nhất.
Nếu chỉ nộp sub này: đúng 19/20 test.
Sub 2: Duyệt đến căn bậc hai — ~O(\sqrt{N})~, dùng khi mọi trường hợp còn lại
Với hai số có tích cố định ~N~, tổng nhỏ nhất khi hai số gần nhau nhất. Vì vậy chỉ cần duyệt ~x~ đến ~\sqrt{N}~ và lấy ước lớn nhất không vượt quá ~\sqrt{N}~, còn ~y = N/x~.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Đề không chia subtask. Sub 1 là cách duyệt trực tiếp khi ~N \le 10^6~, sub 2 là lời giải đầy đủ.
Chương trình đọc ~N~. Nếu ~N \le 10^6~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
long long N;
long long bestX = 1, bestY, bestSum = LLONG_MAX; // cap (x, y) tot nhat
// Sub 1: thu moi x tu 1 den N, neu x chia het N thi xet cap (x, N/x). Dung khi N <= 10^6
void sub1() {
for (long long x = 1; x <= N; x++) {
if (N % x != 0) continue;
long long y = N / x;
if (x <= y && x + y < bestSum) {
bestSum = x + y;
bestX = x;
bestY = y;
}
}
cout << bestX << " " << bestY << "\n";
}
// Sub 2: tong x + y nho nhat khi x gan can bac hai cua N nhat.
// Chi can duyet x tu 1 den sqrt(N), uoc lon nhat <= sqrt(N) cho tong nho nhat.
void sub2() {
long long x = 1;
for (; x * x <= N; x++)
if (N % x == 0) bestX = x; // lay uoc lon nhat (cuoi cung tim thay)
bestY = N / bestX;
cout << bestX << " " << bestY << "\n";
}
int main() {
cin >> N;
if (N <= 1000000) sub1();
else sub2();
return 0;
}
Bình luận