Hướng dẫn giải của [Free Contest 01] KWADRAT
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
Bội số nhỏ nhất của N là số chính phương: với mỗi thừa số nguyên tố p^e của N, nhân thêm để số mũ thành số chẵn nhỏ nhất không nhỏ hơn e.
Sub 1: Thử lần lượt các bội — dùng khi ~N \le 1000~
Thử ~k\cdot N~ với k = 1, 2, ... cho đến khi là số chính phương. Vì ~N^2~ luôn là chính phương nên vòng lặp dừng chậm nhất ở k = N.
Nếu chỉ nộp sub này: đúng 22/22 test.
Sub 2: Phân tích thừa số — ~O(\sqrt{N})~
Phân tích N; với mỗi số mũ lẻ thì tăng thêm 1 và nhân vào đáp án. Thừa số nguyên tố lớn còn lại có mũ 1 nên nhân thêm bình phương của nó. Đáp án tối đa khoảng ~2.5\cdot 10^{17}~ nên dùng số 64 bit.
Nếu chỉ nộp sub này: đúng 22/22 test.
Chương trình hoàn chỉnh
Chương trình đọc N. Nếu N \le 1000 gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
long long N;
bool isSquare(long long m) {
long long s = (long long)sqrtl((long double)m);
while (s * s > m) s--;
while ((s + 1) * (s + 1) <= m) s++;
return s * s == m;
}
// Sub 1: thu lan luot cac boi k*N (k = 1, 2, ...), dung ngay khi gap so chinh phuong.
// Vi N^2 la boi chinh phuong nen vong lap dung khi k <= N. Dung khi N <= 1000
long long sub1() {
for (long long k = 1;; k++) {
if (isSquare(k * N)) return k * N;
}
}
// Sub 2: phan tich N thanh thua so nguyen to, moi so mu lay so chan nho nhat >= mu goc
long long sub2() {
long long n = N, ans = 1;
for (long long p = 2; p * p <= n; p++) {
int e = 0;
while (n % p == 0) {
n /= p;
e++;
}
if (e % 2 == 1) e++;
for (int i = 0; i < e; i++) ans *= p;
}
if (n > 1) ans *= n * n; // thua so nguyen to con lai co mu 1 -> them 1 lan
return ans;
}
int main() {
cin >> N;
if (N <= 1000) cout << sub1() << "\n";
else cout << sub2() << "\n";
return 0;
}
Bình luận