Hướng dẫn giải của Phân tích số (Đề HSG 9 Phú Thọ 2021-2022)
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 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^4)
Thử mọi d từ 2 đến N, đếm d vừa là ước vừa là số nguyên tố. Đúng 15/20 test.
Sub 2: Chia thử đến căn bậc hai, ~O(\sqrt{N})~
Như bài trước: chia thử p đến \sqrt{N}; mỗi p chia hết N tăng đếm 1 và bỏ hết lũy thừa; phần dư > 1 là thừa số nguyên tố. Đúng 20/20 test.
Chương trình hoàn chỉnh
main: N ≤ 10^4 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 so d tu 2 den N; neu d vua la uoc cua N vua la so nguyen to thi dem.
void sub1() {
int cnt = 0;
for (long long d = 2; d <= N; d++)
if (N % d == 0 && isPrime(d)) cnt++;
cout << cnt << "\n";
}
// Sub 2: chia thu p = 2, 3, ... den can bac hai cua N. Moi p chia het N la mot thua so
// nguyen to khac nhau: bo het luy thua cua p, dem cac p nhu vay. Phan du > 1 la so nguyen to.
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;
}
}
if (x > 1) cnt++;
cout << cnt << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
if (N <= 10000) sub1(); // N nho: vet can
else sub2(); // N lon: chia thu den can bac hai
return 0;
}
Bình luận