Hướng dẫn giải của Đếm ước
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
Một ước ~d~ của ~N~ có đúng 4 ước khi và chỉ khi ~d = p^3~ hoặc ~d = p \cdot q~ với ~p, q~ nguyên tố khác nhau. Cần đếm số ước như vậy.
Sub 1: Vét cạn — ~O(N^2)~, dùng khi ~N < 1000~
Liệt kê mọi ước ~d~ của ~N~ rồi đếm số ước của ~d~ bằng vòng lặp. Nếu chỉ nộp sub này: đúng 24/24 test.
Sub 2: Phân tích thừa số — ~O(\sqrt{N})~
Phân tích ~N = \prod p^{e}~. Đếm số ~p~ có ~e \ge 3~ (cho ~d = p^3~), cộng ~\binom{k}{2}~ với ~k~ là số ước nguyên tố khác nhau (cho ~d = p \cdot q~). Nếu chỉ nộp sub này: đúng 24/24 test.
Chương trình hoàn chỉnh
~main~ đọc ~T~ và các ~N~, nếu mọi ~N < 1000~ gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int T;
vector<long long> Nv;
// So uoc nguyen duong cua x (vet can)
long long countDiv(long long x) {
long long c = 0;
for (long long d = 1; d <= x; d++)
if (x % d == 0) c++;
return c;
}
// Sub 1: N < 1000. Liet ke moi uoc d cua N, dem d co dung 4 uoc (vet can truc tiep).
void sub1() {
for (long long N : Nv) {
long long ans = 0;
for (long long d = 1; d <= N; d++)
if (N % d == 0 && countDiv(d) == 4) ans++;
cout << ans << "\n";
}
}
// Sub 2: phan tich N = prod p^e. Uoc d co dung 4 uoc <=> d = p^3 hoac d = p*q (p, q nguyen to khac nhau).
// Dem: so p co e >= 3 (d = p^3), cong C(k,2) voi k = so uoc nguyen to khac nhau (d = p*q).
void sub2() {
for (long long N : Nv) {
long long m = N, k = 0, c = 0;
for (long long p = 2; p * p <= m; p++)
if (m % p == 0) {
int e = 0;
while (m % p == 0) { m /= p; e++; }
k++;
if (e >= 3) c++;
}
if (m > 1) k++; // thua so nguyen to cuoi cung, mu 1
cout << c + k * (k - 1) / 2 << "\n";
}
}
int main() {
cin >> T;
Nv.resize(T);
bool small = true;
for (auto &x : Nv) {
cin >> x;
if (x >= 1000) small = false;
}
if (small) sub1();
else sub2();
return 0;
}
Bình luận