Số Có 9 Ước Số (Bản Khó)
Đề bài
SỐ CÓ 9 ƯỚC SỐ (Bản Khó)
Time limit: 1s
Cho số nguyên dương $N$. Hãy đếm các số nguyên dương không lớn hơn $N$ và có đúng 9 ước số.
Input: Chỉ có 1 dòng ghi số $N$ $(1 \le N \le 10^{14})$.
Output: Ghi ra số lượng các số có 9 ước số.
8888Lời mở đầu
Đây là "bản khó" với $N$ lên tới $10^{14}$, nên đừng nghĩ tới chuyện duyệt từng số từ 1 đến $N$ rồi đếm ước nha các bạn – riêng việc duyệt qua $10^{14}$ số đã mất cả ngày rồi 😅. Để giải được bài này (ít nhất là theo hiểu biết của mình) chỉ có một con đường: phải nắm thật chắc công thức tính số lượng ước từ phân tích thừa số nguyên tố, rồi từ đó suy ngược ra dạng của những số có đúng 9 ước.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJMình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ. Với $N = 888$, có đúng 8 số không vượt quá 888 mà có đúng 9 ước:
| Số | Phân tích | Các ước |
|---|---|---|
| 36 | $2^2 \cdot 3^2$ | 1, 2, 3, 4, 6, 9, 12, 18, 36 |
| 100 | $2^2 \cdot 5^2$ | 1, 2, 4, 5, 10, 20, 25, 50, 100 |
| 196 | $2^2 \cdot 7^2$ | 1, 2, 4, 7, 14, 28, 49, 98, 196 |
| 225 | $3^2 \cdot 5^2$ | 1, 3, 5, 9, 15, 25, 45, 75, 225 |
| 256 | $2^8$ | 1, 2, 4, 8, 16, 32, 64, 128, 256 |
| 441 | $3^2 \cdot 7^2$ | 1, 3, 7, 9, 21, 49, 63, 147, 441 |
| 484 | $2^2 \cdot 11^2$ | 1, 2, 4, 11, 22, 44, 121, 242, 484 |
| 676 | $2^2 \cdot 13^2$ | 1, 2, 4, 13, 26, 52, 169, 338, 676 |
Số tiếp theo có 9 ước là $1089 = 3^2 \cdot 11^2 \gt 888$ nên đáp án là 8.
Nền tảng: công thức đếm số ước
Nếu số $X$ phân tích ra thừa số nguyên tố có dạng $X = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$ (với $p_1, p_2, \ldots$ là các số nguyên tố, $e_1, e_2, \ldots$ là số mũ) thì số lượng ước phân biệt của $X$ là:
tức là lấy các số mũ cộng 1 rồi nhân tích lại. Ví dụ $100 = 2^2 \cdot 5^2$ có $(2 + 1)(2 + 1) = 9$ ước.
Lý do: mỗi ước của $X$ có dạng $p_1^{f_1} \cdots p_k^{f_k}$ với $0 \le f_i \le e_i$, và số mũ $f_i$ có $e_i + 1$ lựa chọn độc lập ⇒ nhân lại.
Vậy số có đúng 9 ước thì tích các $(e_i + 1)$ phải bằng 9. Mà mỗi $e_i \ge 1$ nên mỗi thừa số $(e_i + 1) \ge 2$, và $9$ chỉ tách được thành tích các thừa số $\ge 2$ theo 2 kiểu: $9$ hoặc $3 \times 3$. (Có bạn sẽ nói $1 \times 9$, $1 \times 1 \times 9$ cũng bằng 9 – đúng, nhưng thừa số 1 ứng với số mũ 0, tức là $p^0 = 1$, nghĩa là số nguyên tố đó thực ra không có mặt nên không cần xét.) Từ đó:
Ví dụ: $256 = 2^8$.
Ví dụ: $36 = 2^2 \cdot 3^2$.
Bài toán quy về đếm:
- Trường hợp 1: số các số nguyên tố $p$ thoả $p^8 \le N$.
- Trường hợp 2: số các cặp số nguyên tố $p \lt q$ thoả $p^2 \cdot q^2 \le N$ $\iff$ $p \cdot q \le \sqrt{N}$.
Hai dạng không bao giờ trùng nhau (do phân tích thừa số nguyên tố là duy nhất), nên đáp án là tổng số lượng của cả hai trường hợp. Đến đây là đã nhìn ra bản chất của bài rồi hen 😉. Ta yêu cầu $p \lt q$ vì khi phân tích, các thừa số nguyên tố được viết theo thứ tự tăng dần – nhờ vậy mỗi số chỉ được đếm đúng 1 lần ($2^2 \cdot 3^2$ và $3^2 \cdot 2^2$ là cùng một số 36).
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Vét từng trường hợp với hàm isPrime – chạy được ~90%
Ta cần một hàm kiểm tra số nguyên tố isPrime(x) chạy trong $O(\sqrt{x})$ (thử chia cho các số từ 2 đến $\sqrt{x}$). Hàm này dùng chung cho cả hai trường hợp.
Trường hợp 1: cho $i$ chạy từ 2 (số nguyên tố nhỏ nhất) trở lên, chừng nào $i^8 \le N$ thì nếu $i$ nguyên tố ta tăng biến đếm. Khi $i^8 \gt N$ thì dừng luôn, vì $i$ càng lớn thì $i^8$ càng lớn. Lũy thừa 8 tăng cực nhanh: với $N = 10^{14}$ vòng lặp chỉ chạy tới 56 thôi ($57^8 \approx 1{,}1 \cdot 10^{14} \gt 10^{14}$), và mỗi lần isPrime chỉ thử vài số chia (với 57 chỉ thử tới 7) ⇒ trường hợp này gần như không tốn gì.
Trường hợp 2 mới là phần nặng. Đặt $X = \lfloor\sqrt{N}\rfloor$, ta cần đếm cặp nguyên tố $a \lt b$ với $a \cdot b \le X$:
- Vì $a \lt b$ và $a \cdot b \le X$ nên $a^2 \lt X$, tức là $a$ chỉ cần xét tới $\sqrt{X}$. (Nếu $a \gt \sqrt{X}$ thì để $a \cdot b \le X$ buộc $b \lt \sqrt{X} \lt a$, trái với $a \lt b$.)
- Với mỗi $a$ nguyên tố, $b$ phải thoả $a \lt b \le X / a$. Ta cho $b$ chạy từ $X / a$ giảm dần tới khi $b \le a$ thì dừng, gặp $b$ nguyên tố thì tăng biến đếm.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
/* Hàm kiểm tra số nguyên tố với độ phức tạp O(sqrt(X)) với X là số cần kiểm tra */
bool isPrime(long long x){
for(long long i = 2; i * i <= x; ++i){
if(x % i == 0){
return false;
}
}
return true;
}
int main(){
long long n;
cin >> n;
long long cnt = 0;
/* Trường hợp 1: Đếm tất cả các số nguyên tố thoả mãn luỹ thừa 8 mà <= n */
for(long long i = 2; (long long)pow(i, 8) <= n; ++i){
if(isPrime(i)){
cnt++;
}
}
/* Trường hợp 2: Đếm tất cả các số nguyên tố a, b thoả mãn a < b và a^2 * b^2 <= n */
long long x = (long long)sqrt(n);
long long sqrt_x = (long long)sqrt(x);
for(long long a = 2; a <= sqrt_x; ++a){
if(isPrime(a)){
for(long long b = x / a; b > a; --b){
if(isPrime(b)){
cnt++;
}
}
}
}
cout << cnt;
return 0;
}import math
# Hàm kiểm tra số nguyên tố với độ phức tạp O(sqrt(X))
def is_prime(x):
i = 2
while i * i <= x:
if x % i == 0:
return False
i += 1
return True
n = int(input())
cnt = 0
# Trường hợp 1: đếm các số nguyên tố i thoả i^8 <= n
i = 2
while i ** 8 <= n:
if is_prime(i):
cnt += 1
i += 1
# Trường hợp 2: đếm các cặp nguyên tố a < b thoả a^2 * b^2 <= n
x = math.isqrt(n)
sqrt_x = math.isqrt(x)
for a in range(2, sqrt_x + 1):
if is_prime(a):
b = x // a
while b > a:
if is_prime(b):
cnt += 1
b -= 1
print(cnt)Bản Python dùng math.isqrt để lấy căn nguyên chính xác. Các bạn chạy tay với $N = 888$ để thấy từng số được đếm (bên phần Dữ liệu có danh sách các số đã đếm được):
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(1)$.
- Thời gian: Trường hợp 1 là $O(N^{1/8})$ (vòng
for i) $\times$ $O(N^{1/16})$ (kiểm tra nguyên tố của $i$) – không đáng kể. Trường hợp 2 là $O(N^{1/4})$ (vòngfor a) $\times$ [$O(N^{1/8})$ (kiểm tra $a$) + $O(N^{1/2})$ (vòngfor b) $\times$ $O(N^{1/4})$ (kiểm tra $b$)] ⇒ tính thô theo trường hợp xấu nhất thì cỡ $O(N)$.
Thực tế không tệ đến vậy: con số trên chỉ là chặn trên lý thuyết. Vòng for b chỉ chạy khi $a$ nguyên tố, độ dài của nó là $X/a$ giảm rất nhanh khi $a$ tăng, và isPrime(b) với $b$ là hợp số thường dừng sớm (đa số chia hết cho 2, 3, 5...). Vì vậy code này nộp được 90/100, chỉ 10 test cuối bị TLE.
isPrime bị gọi liên tục qua 2 vòng lặp lồng nhau, kiểm tra đi kiểm tra lại tính nguyên tố của cùng những số $b$ (với $a = 2$, $a = 3$, $a = 5$... các khoảng $b$ chồng lên nhau), và còn tốn công kiểm tra cả những $b$ không phải số nguyên tố.Cách 2Sàng Eratosthenes + tìm kiếm nhị phân – O(√N log log √N)
Như mình nói, bài này chỉ có một hướng (xử lý 2 trường hợp), nên ta không cần nghĩ ra cách khác mà chỉ cần nhìn ra những chỗ chưa tốt của Cách 1 rồi khắc phục:
- Bỏ việc gọi isPrime lặp đi lặp lại. Ngay từ đầu ta tìm hết các số nguyên tố trong phạm vi cần thiết rồi đưa vào một mảng $a$. Chấp nhận tốn thêm bộ nhớ, nhưng bù lại chỉ duyệt trên số nguyên tố, và việc "xác định nguyên tố" chỉ làm đúng một lần. Phạm vi cần thiết là $\le \sqrt{N}$, vì $a^2 b^2 \le N \iff a \cdot b \le \sqrt{N}$. Và ta không kiểm tra từng số bằng
isPrimenữa mà dùng sàng Eratosthenes cho tối ưu. - Đếm bằng tìm kiếm nhị phân thay vì duyệt tuần tự. Mảng số nguyên tố sinh ra từ sàng luôn tăng dần, nên đếm "có bao nhiêu số nguyên tố $\le$ giá trị nào đó" chỉ cần tìm vị trí phần tử đầu tiên lớn hơn giá trị đó, dùng
upper_boundcó sẵn trong STL.
- Trường hợp 1: $x = \lfloor N^{1/8} \rfloor$.
upper_bound(a, x)trả về vị tríidxcủa số nguyên tố đầu tiên $\gt x$. Vì mảng đánh chỉ số từ 0 nên có đúngidxsố nguyên tố $\le x$ ⇒cnt = idx. - Trường hợp 2: với mỗi $a[i]$ còn thoả $a[i]^4 \le N$ (tức $a[i] \le N^{1/4}$), đặt $x = \lfloor\sqrt{N}\rfloor / a[i]$, tìm
j = upper_boundtrong đoạn bắt đầu từ $i$. Các $b$ hợp lệ là $a[i+1], \ldots, a[j-1]$ ⇒ cộng thêm $j - i - 1$.
Minh hoạ: sàng xong rồi đếm bằng upper_bound
Em nhập $N$ rồi bấm Tiếp. Ô vàng là $a[i]$ đang xét, các ô xanh là những $b$ được đếm (từ $a[i+1]$ tới ngay trước vị trí upper_bound), ô có viền là vị trí upper_bound trả về:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n;
cin >> n;
/* Bước sàng nguyên tố */
long long sz = (long long)sqrt(n);
vector<bool> checkPrime(sz + 1, true);
checkPrime[0] = false;
checkPrime[1] = false;
vector<long long> a;
for(long long i = 2; i <= sz; ++i){
if(checkPrime[i] == true){
a.push_back(i);
for(long long j = i * i; j <= sz; j += i){
checkPrime[j] = false;
}
}
}
/* Xử lý trường hợp 1 */
long long x = (long long)pow(n, 1.0 / 8);
vector<long long>::iterator upper;
upper = upper_bound(a.begin(), a.end(), x);
long long cnt = upper - a.begin();
/* Xử lý trường hợp 2 */
for(long long i = 0; i < a.size(); i++){
if(pow(a[i], 4) > n){
break;
}
x = sz / a[i];
upper = upper_bound(a.begin() + i, a.end(), x);
cnt += upper - (a.begin() + i) - 1;
}
cout << cnt;
return 0;
}import math
from bisect import bisect_right
n = int(input())
# Bước sàng nguyên tố đến sz = sqrt(n)
sz = math.isqrt(n)
check_prime = bytearray([1]) * (sz + 1)
check_prime[0] = 0
if sz >= 1:
check_prime[1] = 0
for i in range(2, math.isqrt(sz) + 1):
if check_prime[i]:
check_prime[i * i::i] = bytes(len(range(i * i, sz + 1, i)))
a = [i for i in range(2, sz + 1) if check_prime[i]]
# Xử lý trường hợp 1: số nguyên tố p với p^8 <= n
x = math.isqrt(math.isqrt(math.isqrt(n))) # căn bậc 8 của n (lấy phần nguyên)
cnt = bisect_right(a, x)
# Xử lý trường hợp 2: cặp a[i] < b với a[i] * b <= sz
for i in range(len(a)):
if a[i] ** 4 > n:
break
x = sz // a[i]
j = bisect_right(a, x, i)
cnt += j - i - 1
print(cnt)bool checkPrime[sz + 1]; – đây là mảng có độ dài biến (VLA), không thuộc C++ chuẩn và nằm trên stack. Với $N = 10^{14}$ thì $sz = 10^7$, mảng chiếm 10 MB stack. Hệ thống chấm cho stack lớn thì không sao, nhưng trên máy có stack mặc định 8 MB (như máy mình thử) chương trình bị Segmentation fault ngay. Nên mình đổi sang vector<bool> checkPrime(sz + 1, true); (cấp phát trên heap, còn gọn hơn vì khởi tạo true luôn), logic giữ nguyên.(long long)pow(n, 1.0 / 8) và (long long)sqrt(n) tính bằng số thực nên về lý thuyết có thể lệch 1 ở sát biên. Mình đã kiểm tra trực tiếp: với mọi số nguyên tố $p \le 59$ và $n \in \{p^8 - 1, p^8\}$, cũng như mọi $n \in \{k^2 - 1, k^2\}$ với $k \le 10^7$, kết quả đều đúng trong phạm vi $N \le 10^{14}$. Bản Python thì mình dùng math.isqrt (căn nguyên chính xác; căn bậc 8 = isqrt lồng 3 lần) cho chắc ăn.Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(M + K)$ với $M = \sqrt{N}$ là kích thước mảng
checkPrime, $K$ là số lượng số nguyên tố trong mảng $a$ ($K \lt M$). Tính tổng quát cứ xem như $O(2\sqrt{N}) = O(\sqrt{N})$. - Thời gian: Bước sàng Eratosthenes đến $\sqrt{N}$ tốn $O(\sqrt{N} \log\log\sqrt{N})$ – nếu tính rộng tay là $O(\sqrt{N} \log \sqrt{N})$ thì vẫn là chặn trên đúng. Trường hợp 1 không đáng kể. Trường hợp 2 vòng lặp chạy chỉ tới các số nguyên tố $\le N^{1/4}$, mỗi lần tốn một lần tìm kiếm nhị phân $O(\log \sqrt{N})$ – nhỏ hơn hẳn bước sàng.
Theo quy tắc cộng của Big-O thì lấy bước lớn nhất là bước sàng.
Vậy cách này chấp nhận tốn thêm bộ nhớ (với $N = 10^{14}$ là mảng sàng $10^7$ phần tử) nhưng thời gian giảm từ cỡ $O(N)$ xuống chỉ còn quanh $O(\sqrt{N})$. Kể cả $N = 10^{14}$ cũng không sợ TLE nữa. Các bạn đã thấy cái hay của thuật toán chưa 🥰
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét