Hướng dẫn giải của Số ước nguyên tố (Đề HSG Nghệ An 2021)
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
Số ước nguyên tố của n chính là số thừa số nguyên tố khác nhau của n.
Sub 1: Vét cạn, ~O(n \sqrt{n})~ (n ≤ 10^3)
Thử mọi d từ 1 đến n, đếm d vừa là ước vừa là số nguyên tố. Đúng 17/20 test.
Sub 2: Phân tích thừa số, ~O(\sqrt{n})~
Chia thử p = 2, 3, ... với p^2 ≤ n; mỗi p chia hết n thì tăng đếm 1 và bỏ hết lũy thừa của p; phần dư > 1 là một thừa số nguyên tố. Đúng 20/20 test.
Chương trình hoàn chỉnh
main: n ≤ 1000 gọi sub1, còn 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;
long long n;
// Kiem tra x co phai so nguyen to khong (chia thu)
bool isPrime(long long x) {
if (x < 2) return false;
for (long long d = 2; d * d <= x; d++)
if (x % d == 0) return false;
return true;
}
// Sub 1: vet can. Thu moi uoc d cua n (d tu 1 den n), dem nhung uoc la so nguyen to
void sub1() {
int cnt = 0;
for (long long d = 1; d <= n; d++)
if (n % d == 0 && isPrime(d)) cnt++;
cout << cnt << "\n";
}
// Sub 2: phan tich n. Moi uoc nguyen to cua n la mot thua so nguyen to khac nhau,
// nen chi can chia thu cac so p = 2, 3, ... va dem so p chia het n (p*p <= n).
void sub2() {
long long x = n;
int cnt = 0;
for (long long p = 2; p * p <= x; p++) {
if (x % p == 0) {
cnt++;
while (x % p == 0) x /= p; // bo het luy thua cua p
}
}
if (x > 1) cnt++; // phan du con lai la mot so nguyen to lon
cout << cnt << "\n";
}
int main() {
freopen("uocnt.inp", "r", stdin);
freopen("uocnt.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận