Hướng dẫn giải của F18: Ước chẵn, ước 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
Với T <= 100 số n (n <= 10^18), f(n) là số ước dương của n. In CHAN nếu f(n) chẵn, LE nếu f(n) lẻ.
Sub 1: Đếm ước bằng cách thử đến căn bậc hai — ~O(sqrt(n))~
Đếm số ước của n bằng cách thử i từ 1 đến sqrt(n). Với n đến 10^18 thì quá chậm: 6 test bị TLE.
Kết quả chấm: đạt 14/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
long long n;
cin >> n;
// Vet can: dem so uoc cua n bang cach thu i tu 1 den sqrt(n)
long long cnt = 0;
for (long long i = 1; i * i <= n; i++) {
if (n % i == 0) {
if (i * i == n) cnt += 1;
else cnt += 2;
}
}
cout << (cnt % 2 == 0 ? "CHAN" : "LE") << "\n";
}
return 0;
}
Sub 2: Số ước lẻ khi và chỉ khi n là số chính phương — ~O(1)~
Các ước ghép thành cặp (i, n/i), chỉ có cặp i = n/i (tức n = i*i) mới làm số ước lẻ. Kiểm tra n có phải số chính phương bằng sqrtl rồi chỉnh r ±1 để tránh sai số số thực. Nếu là chính phương thì LE, nếu không thì CHAN.
Kết quả chấm: đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
// f(n) la so le khi va chi khi n la so chinh phuong (uoc i ghep voi n/i, chi uoc can bang nhau la le)
bool laChinhPhuong(long long n) {
long long r = (long long)sqrtl((long double)n);
while (r * r > n) r--;
while ((r + 1) * (r + 1) <= n) r++;
return r * r == n;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
long long n;
cin >> n;
cout << (laChinhPhuong(n) ? "LE" : "CHAN") << "\n";
}
return 0;
}
Bình luận