Hướng dẫn giải của [VTT Q4 Contest 07] Bài 4: Lũy thừa [POWER]
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
Đếm cặp ~(i, j)~ sao cho ~a_i \cdot a_j~ là lũy thừa bậc ~k~ của một số nguyên. Tích là lũy thừa bậc ~k~ khi và chỉ khi số mũ của mỗi nguyên tố trong tích chia hết cho ~k~.
Sub 1: Vét cạn — ~O(n^2 \log)~, dùng khi ~n \le 1000~
Phân tích sẵn mỗi ~a_i~ ra thừa số nguyên tố (sàng ước nguyên tố nhỏ nhất). Với mỗi cặp, cộng số mũ của hai số rồi kiểm tra mọi số mũ có chia hết cho ~k~ không. Nếu chỉ nộp sub này: đúng 11/40 test.
Sub 2: Đặc trưng mod ~k~ và đếm bằng map — ~O(n \log n)~
Với mỗi ~a_i~, chỉ giữ lại các nguyên tố có số mũ khác 0 theo modulo ~k~, cùng số mũ đó: gọi là đặc trưng. Hai số ghép được khi đặc trưng của số này là "bù" của số kia, tức cùng tập nguyên tố và các số mũ cộng lại bằng ~k~. Duyệt ~i~ từ trái sang phải, cộng số lần đã gặp đặc trưng bù của ~a_i~, rồi thêm đặc trưng của ~a_i~ vào map. Số 1 (và mọi lũy thừa bậc ~k~) có đặc trưng rỗng, bù của nó cũng rỗng nên tự ghép với nhau. Đáp án có thể tới ~5 \cdot 10^9~, phải dùng long long. Nếu chỉ nộp sub này: đúng 40/40 test.
Chương trình hoàn chỉnh
main sàng ước nguyên tố nhỏ nhất, đọc dữ liệu; ~n \le 1000~ gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
const int MAXA = 100005;
int n, k;
int a[MAXA];
int spf[MAXA]; // ước nguyên tố nhỏ nhất
// Phân tích x thành các cặp (nguyên tố, số mũ mod k), bỏ các số mũ chia hết cho k
vector<pair<int,int>> sig(int x) {
vector<pair<int,int>> r;
while (x > 1) {
int p = spf[x], e = 0;
while (x % p == 0) { x /= p; e++; }
e %= k;
if (e) r.push_back({p, e});
}
return r; // các nguyên tố tăng dần
}
// Sub 1: xét mọi cặp, ghép hai đặc trưng rồi kiểm tra — O(n^2 log)
void sub1() {
vector<vector<pair<int,int>>> s(n + 1);
for (int i = 1; i <= n; i++) s[i] = sig(a[i]);
long long ans = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++) {
map<int,int> m;
for (auto &q : s[i]) m[q.first] += q.second;
for (auto &q : s[j]) m[q.first] += q.second;
bool ok = true;
for (auto &q : m) if (q.second % k) { ok = false; break; }
if (ok) ans++;
}
cout << ans << "\n";
}
// Sub 2: đếm bằng map theo đặc trưng; cần đặc trưng "bù" của mỗi số — O(n log)
void sub2() {
map<vector<pair<int,int>>, int> cnt;
long long ans = 0;
for (int i = 1; i <= n; i++) {
auto s = sig(a[i]);
auto c = s;
for (auto &q : c) q.second = k - q.second; // số mũ bù để tổng chia hết cho k
auto it = cnt.find(c);
if (it != cnt.end()) ans += it->second;
cnt[s]++;
}
cout << ans << "\n";
}
int main() {
freopen("POWER.INP", "r", stdin);
freopen("POWER.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
for (int i = 2; i < MAXA; i++)
if (!spf[i])
for (int j = i; j < MAXA; j += i)
if (!spf[j]) spf[j] = i;
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
if (n <= 1000) sub1();
else sub2();
}
Bình luận