Hướng dẫn giải của [KSCUM VT 02] CÂU 2: Tổng số mũ chẵn lẻ
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
Phân tích ~N = p_1^{x_1} \cdots p_k^{x_k}~, cộng các số mũ chẵn vào ~S~ và các số mũ lẻ vào ~P~. Đề yêu cầu đọc file ~CAU2.INP~ và ghi ra ~CAU2.OUT~ gồm hai dòng ~S~ và ~P~.
Sub 1: Thử mọi d từ 2 đến N — ~O(N)~, dùng khi ~N \le 10^6~
Thử chia lần lượt mọi ~d = 2 \dots N~, đếm số mũ của mỗi thừa số. Nếu chỉ nộp sub này: đúng 12/20 test (8 test lớn quá giờ khi chạy riêng).
Sub 2: Chia thử đến căn bậc hai — ~O(\sqrt{N})~
Chia thử ~d~ đến ~d^2 \le m~, thừa số cuối còn lại (nếu lớn hơn 1) là số nguyên tố có mũ 1 nên cộng 1 vào ~P~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
~main~ đọc ~N~, nếu ~N \le 10^6~ gọi sub1, ngược lại gọi sub2, rồi in ~S~ và ~P~.
#include <bits/stdc++.h>
using namespace std;
long long N;
long long S = 0, P = 0; // S: tong cac so mu chan, P: tong cac so mu le
// Sub 1: N <= 10^6. Thu chia lan luot moi d = 2..N (vet can), dem so mu cua moi thua so nguyen to.
void sub1() {
long long m = N;
for (long long d = 2; d <= N; d++) {
int e = 0;
while (m % d == 0) { m /= d; e++; }
if (e > 0) {
if (e % 2 == 0) S += e;
else P += e;
}
}
}
// Sub 2: N <= 10^12. Chia thu den can(N) va xu ly thua so nguyen to cuoi cung (mu 1, le).
void sub2() {
long long m = N;
for (long long d = 2; d * d <= m; d++) {
int e = 0;
while (m % d == 0) { m /= d; e++; }
if (e > 0) {
if (e % 2 == 0) S += e;
else P += e;
}
}
if (m > 1) P += 1;
}
int main() {
freopen("CAU2.INP", "r", stdin); // may cham doc/ghi file
freopen("CAU2.OUT", "w", stdout);
cin >> N;
if (N <= 1000000) sub1();
else sub2();
cout << S << "\n" << P << "\n";
return 0;
}
Bình luận