Hướng dẫn giải của [Beginner Free Contest 03] NHANTINH
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
Dãy là nhân tính hoàn toàn khi ~a_{ij} = a_i a_j~ với mọi ~i, j~ mà ~ij \le n~. Chỉ cần kiểm tra các cặp (i, j) có tích không vượt quá n.
Sub 1: Kiểm tra mọi cặp — ~O(n^2)~, dùng khi ~n \le 1000~
Duyệt mọi cặp i, j trong [1..n] mà ~i\cdot j \le n~ và kiểm tra ~a_{ij} = a_i a_j~. Tích có thể lên tới ~10^{18}~ nên dùng số 64 bit.
Nếu chỉ nộp sub này: đúng 49/50 test (test còn lại vượt miền n).
Sub 2: Duyệt theo điều hòa — ~O(n\log n)~
Với mỗi i, chỉ xét j từ 1 đến ~\lfloor n/i \rfloor~ vì các cặp khác không thỏa ~ij \le n~. Tổng số cặp cần xét là khoảng ~n\ln n~.
Nếu chỉ nộp sub này: đúng 50/50 test.
Chương trình hoàn chỉnh
Chương trình đọc n và dãy. Nếu n \le 1000 gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a; // a[1..n]
// Sub 1: kiem tra moi cap (i, j) sao cho i*j <= n. O(n^2). Dung khi n <= 1000
bool sub1() {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i * j <= n && a[i * j] != a[i] * a[j]) return false;
return true;
}
// Sub 2: voi moi i, chi xet j sao cho i*j <= n (dieu hien nhien). Tong cac phep xet la O(n log n)
bool sub2() {
for (int i = 1; i <= n; i++)
for (int j = 1; (long long)i * j <= n; j++)
if (a[i * j] != a[i] * a[j]) return false;
return true;
}
int main() {
cin >> n;
a.assign(n + 1, 0);
for (int i = 1; i <= n; i++) cin >> a[i];
if (n <= 1000) cout << (sub1() ? "YES" : "NO") << "\n";
else cout << (sub2() ? "YES" : "NO") << "\n";
return 0;
}
Bình luận