Hướng dẫn giải của CAU1
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
Cho đoạn [l, r] (l, r ≤ 10^4 theo đề, bộ test thực tế có r lớn hơn), đếm số x trong đoạn có tổng các ước nguyên dương là số nguyên tố. Gọi f(x) là tổng các ước của x.
Sub 1: Vét cạn — ~O(n^2)~
Với mỗi x trong [l, r], thử mọi số d từ 1 đến x để tìm ước rồi cộng lại thành f(x). Sau đó kiểm tra f(x) có phải số nguyên tố bằng cách thử các ước. Đạt 18/24 test, các test còn lại quá chậm (TLE).
Kết quả chấm: 18/24 (SUB ok 18/24, TLE 6, WA 0)
#include <bits/stdc++.h>
using namespace std;
// Kiem tra nguyen to bang cach thu moi uoc
bool laNguyenTo(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;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU1.INP", "r")) { freopen("CAU1.INP", "r", stdin); freopen("CAU1.OUT", "w", stdout); }
int l, r;
cin >> l >> r;
int dem = 0;
// Vet can: voi moi x trong [l, r], tim tat ca uoc bang cach thu tu 1 den x
for (int x = l; x <= r; x++) {
long long tong = 0;
for (int d = 1; d <= x; d++)
if (x % d == 0) tong += d;
if (laNguyenTo(tong)) dem++;
}
cout << dem << "\n";
return 0;
}
Sub 2: Sàng tổng ước và sàng nguyên tố — ~O(n \log n)~
Thay vì thử từng ước, dùng sàng: với mỗi d, cộng d vào f(m) của mọi bội m của d. Sau đó sàng nguyên tố tới giá trị lớn nhất của f và tra bảng cho từng x.
Bẫy: f(x) lớn hơn x nên không được sàng nguyên tố chỉ tới r; phải sàng tới đúng giá trị max f(x) trong đoạn. Dùng long long khi cộng tổng.
Kết quả chấm: 24/24
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU1.INP", "r")) { freopen("CAU1.INP", "r", stdin); freopen("CAU1.OUT", "w", stdout); }
int l, r;
cin >> l >> r;
// sigma[x] = tong cac uoc nguyen duong cua x. Sang dieu hoa: moi d la uoc cua cac boi so cua no
vector<long long> sigma(r + 1, 0);
for (int d = 1; d <= r; d++)
for (int m = d; m <= r; m += d)
sigma[m] += d;
// Tim tong uoc lon nhat de sang so nguyen to toi do (tong uoc luon nho hon 6 lan so do voi n <= 10^9)
long long maxS = 0;
for (int x = l; x <= r; x++) maxS = max(maxS, sigma[x]);
vector<bool> isPrime(maxS + 1, true);
isPrime[0] = false;
if (maxS >= 1) isPrime[1] = false;
for (long long i = 2; i * i <= maxS; i++)
if (isPrime[i])
for (long long j = i * i; j <= maxS; j += i)
isPrime[j] = false;
int dem = 0;
for (int x = l; x <= r; x++)
if (isPrime[sigma[x]]) dem++;
cout << dem << "\n";
return 0;
}
Bình luận