Hướng dẫn giải của Hình chữ nhật đẹp
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
Hình chữ nhật có cạnh ~x~ và ~y~ là “đẹp” khi ~x \cdot y~ là số chính phương. Cần tìm ~y~ nguyên dương nhỏ nhất với ~x \le 10^{12}~.
Sub 1: Vét cạn — ~O(x)~, dùng khi ~x \le 10^6~
Thử ~y = 1, 2, 3, ...~ và dừng khi ~x \cdot y~ là số chính phương (kiểm tra bằng căn bậc hai). Đáp số không vượt quá ~x~ vì ~x \cdot x~ luôn là số chính phương. Nếu chỉ nộp sub này: đúng 27/30 test.
Sub 2: Phân tích thừa số — ~O(\sqrt{x})~, dùng cho ~x \le 10^{12}~
Phân tích ~x~ thành các thừa số nguyên tố. ~x \cdot y~ là chính phương khi và chỉ khi mọi số mũ trong ~x \cdot y~ đều chẵn, nên ~y~ nhỏ nhất bằng tích các số nguyên tố có số mũ lẻ trong ~x~. Bẫy: đừng để ~x \cdot y~ tràn số (không cần tính nó). Chạy riêng sub này: đúng 30/30 test.
Chương trình hoàn chỉnh
Chương trình đọc ~x~; nếu ~x \le 10^6~ gọi sub1, ngược lại gọi sub2. Sub 2 đúng với mọi ~x~ nên đây là lời giải đầy đủ.
Số test: 30 (chương trình đầy đủ đúng 30/30).
#include <bits/stdc++.h>
using namespace std;
long long x;
// Kiem tra v co phai so chinh phuong khong
bool isSquare(long long v) {
long long r = (long long)sqrtl((long double)v);
while (r * r > v) r--;
while ((r + 1) * (r + 1) <= v) r++;
return r * r == v;
}
// Sub 1: vet can. Thu y = 1, 2, 3, ... cho den khi x*y la so chinh phuong
// (y <= x luon thoa, nen vong lap ket thuc). Dung khi x <= 10^6
void sub1() {
for (long long y = 1;; y++)
if (isSquare(x * y)) {
cout << y << "\n";
return;
}
}
// Sub 2: day du. x*y la so chinh phuong khi va chi khi moi so mu trong phan tich x*y la chan.
// Vay y phai nhan them dung cac so nguyen to co so mu le trong x, va y nho nhat = tich cac
// so nguyen to co so mu le trong x. Dung cho moi x <= 10^12.
void sub2() {
long long m = x, y = 1;
for (long long p = 2; p * p <= m; p++) {
int e = 0;
while (m % p == 0) {
m /= p;
e++;
}
if (e % 2 == 1) y *= p; // so mu le: can nhan them p
}
if (m > 1) y *= m; // so nguyen to lon con lai co mu 1
cout << y << "\n";
}
int main() {
freopen("B1.INP", "r", stdin);
freopen("B1.OUT", "w", stdout);
cin >> x;
if (x <= 1000000) sub1();
else sub2();
return 0;
}
Bình luận