NUM5 (final2_2122_num5)

Nguồn: HNOJ – final2 2021-2022 Độ khó: Trung bình Số học Vét cạn Sắp xếp Tìm kiếm nhị phân

Đề bài

2. num5

Một số được gọi là NUM5 nếu số đó có ước nguyên tố lớn nhất không vượt quá 5. Ví dụ số NUM5 là: $3, 10$; số không phải số NUM5 là: $7, 44$. Hỏi với một số nguyên $N$, hãy kiểm tra xem $N$ có phải là số NUM5 không và có bao nhiêu số NUM5 không lớn hơn $N$.

Dữ liệu: Vào từ file văn bản NUM5.INP có khuôn dạng sau:

• Dòng đầu tiên gồm một số nguyên dương $T$ là số bộ test $(T \le 10^5)$;
• $T$ dòng sau, mỗi dòng gồm một số nguyên dương $N$ mô tả một bộ test $(N \le 10^9)$.

Kết quả: Ghi ra file văn bản NUM5.OUT gồm $T$ dòng, mỗi dòng in kết quả của một bộ test tương ứng có cấu trúc như sau:

• Nếu $N$ không phải là số NUM5 thì in ra "NO";
• Ngược lại, in ra "YES x" với $x$ là số lượng số NUM5 không lớn hơn $N$.

Ràng buộc:

• Có 30% số test tương ứng với 30% số điểm có $T \le 10^2$; $N \le 10^6$;
• 20% số test khác tương ứng với 20% số điểm có $T \le 10^5$; $N \le 10^6$;
• 50% số test còn lại tương ứng với 50% số điểm không có ràng buộc gì thêm.

Trên hệ thống chấm online thì đọc dữ liệu từ bàn phím và in ra màn hình.

Ví dụ – NUM5.INP

4
1
10
7
44

Ví dụ – NUM5.OUT

YES 1
YES 9
NO
NO

Giải thích: khi $N = 10$, các số NUM5 thoả mãn: $1, 2, 3, 4, 5, 6, 8, 9, 10$.

Lời mở đầu

Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình chia sẻ đề bài để các bạn thử sức làm, kèm theo lời giải chi tiết để bạn nào không giải quyết được thì có thể tham khảo nhen. Hi vọng mang đến được giá trị cho các bạn 😇.

Nhắc lại ngưỡng TLE

Với giới hạn 1 giây, tối đa toàn bài chỉ nên lặp khoảng $10^8$ lần (với C/C++); Python chạy chậm hơn nhiều nên ngưỡng phải thấp hơn hẳn.

Giải thích đề cho bạn nào chưa hiểu: số NUM5 là số mà khi phân tích ra thừa số nguyên tố thì chỉ có các thừa số 2, 3, 5. Ví dụ $10 = 2 \cdot 5$ là NUM5; $44 = 2^2 \cdot 11$ có ước nguyên tố 11 > 5 nên không phải; $7$ là số nguyên tố lớn hơn 5 nên cũng không phải. Riêng số $1$ không có ước nguyên tố nào, đề tính nó là NUM5 (ví dụ $N = 1$ in YES 1). Với mỗi $N$: nếu $N$ là NUM5 thì in YES kèm số lượng số NUM5 từ 1 đến $N$, ví dụ $N = 10$ có 9 số $1, 2, 3, 4, 5, 6, 8, 9, 10$ ⇒ YES 9; nếu không thì chỉ in NO.

Link nộp bài

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 OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Mỗi truy vấn duyệt 3 vòng lặp p2, p3, p5 · O(T · K)Cách 2Sinh hết số NUM5 ≤ 10^9, sắp xếp, chặt nhị phân · O(K log K + T log K)

Cách 1Duyệt 3 vòng lặp cho mỗi truy vấn – O(T · K)

Số có các ước nguyên tố $\le 5$ thì nó chỉ gồm 2, 3, 5 thôi. Có nghĩa là số đó có dạng:

Dạng của số NUM5

$2^{p_2} \cdot 3^{p_3} \cdot 5^{p_5}$, với $p_2, p_3, p_5 \ge 0$

Vậy duyệt 3 vòng for lồng nhau $p_2$, $p_3$, $p_5$ là sinh ra được hết các số NUM5 $\le N$: vừa đếm được có bao nhiêu số, vừa kiểm tra được trong đó có số nào bằng đúng $N$ không. Vì mỗi bộ $(p_2, p_3, p_5)$ cho ra một số khác nhau (phân tích thừa số nguyên tố là duy nhất) nên đếm như vậy không bị trùng.

Với $N \le 10^9$ thì $p_2$ chỉ có tầm 30 giá trị ($2^{29} < 10^9 < 2^{30}$), $p_3$ khoảng 19 giá trị, $p_5$ khoảng 13 giá trị. Ước lượng thô theo kiểu nhân hết lại thì khoảng vài nghìn bộ cho mỗi truy vấn, mà có tối đa $T = 10^5$ truy vấn ⇒ cỡ $10^8$ đến $4 \cdot 10^8$ phép tính. Cũng căng, có khả năng TLE vì ngưỡng 1 giây chỉ khoảng $10^8$ thôi. Cần tối ưu lại một chút (xem cách 2).

Thực tế đếm chính xác

Vòng lặp dừng ngay khi tích vượt $N$ nên số bộ thực sự duyệt đúng bằng số lượng số NUM5 $\le N$. Mình cho máy đếm thì chỉ có 1530 số NUM5 $\le 10^9$. Nên trường hợp xấu nhất là $1530 \cdot 10^5 \approx 1{,}5 \cdot 10^8$ lần lặp, vẫn sát ngưỡng.

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);
    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        int cnt = 0;
        bool isNum5 = false;
        for (long long x = 1; x <= n; x *= 2) {             // x = 2^p2
            for (long long y = x; y <= n; y *= 3) {         // y = 2^p2 * 3^p3
                for (long long z = y; z <= n; z *= 5) {     // z = 2^p2 * 3^p3 * 5^p5
                    cnt++;
                    if (z == n) {
                        isNum5 = true;
                    }
                }
            }
        }
        if (isNum5) {
            cout << "YES " << cnt << "\n";
        }
        else {
            cout << "NO\n";
        }
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    out = []
    for k in range(1, t + 1):
        n = int(data[k])
        cnt = 0
        is_num5 = False
        x = 1
        while x <= n:                 # x = 2^p2
            y = x
            while y <= n:             # y = 2^p2 * 3^p3
                z = y
                while z <= n:         # z = 2^p2 * 3^p3 * 5^p5
                    cnt += 1
                    if z == n:
                        is_num5 = True
                    z *= 5
                y *= 3
            x *= 2
        out.append("YES " + str(cnt) if is_num5 else "NO")
    print("\n".join(out))

main()

Đánh giá độ phức tạp: gọi $K$ là số lượng số NUM5 $\le 10^9$ ($K = 1530$). Mỗi truy vấn tốn $O(K)$ ⇒ tổng $O(T \cdot K)$, bộ nhớ $O(1)$.

Không gian$O(1)$

Thời gian$O(T \cdot K)$

Chạy thử thực tế

Trên máy mình, với $T = 10^5$ và $N$ đến $10^9$: bản C++ chạy khoảng 0.2 giây (vòng lặp rất đơn giản nên máy chạy nhanh hơn ước lượng), nhưng bản Python mất khoảng 23 giây ⇒ chắc chắn TLE. Kết quả của C++ còn tuỳ máy chấm, nên an toàn nhất vẫn là cách 2 bên dưới.

Cách 2Sinh hết số NUM5 ≤ 10^9, sắp xếp rồi chặt nhị phân – O(K log K + T log K)

Để ý cách 1 làm đi làm lại cùng một việc cho mọi truy vấn. Vậy đầu tiên ta sinh ra toàn bộ các số $\le 1$ tỷ mà chỉ có 3 ước nguyên tố 2, 3, 5 (chỉ làm một lần), xong rồi sắp xếp tụi nó lại. Với mỗi số $N$, ta chặt nhị phân tìm vị trí của $N$ trong mảng:

• Nếu tìm thấy $N$ ở vị trí pos (đánh số từ 0) thì $N$ là NUM5, và các số NUM5 $\le N$ chính là các phần tử từ đầu mảng đến vị trí đó ⇒ có pos + 1 số ⇒ in YES pos+1.
• Không thấy thì in NO.

Các bạn nhìn bản nháp này sẽ rõ, mỗi dòng là một bộ $(p_2, p_3, p_5)$ và số tương ứng (mình làm mẫu nhanh, còn thiếu nhiều bộ, nhưng đại ý là cứ xét hết những số $\le 1$ tỷ rồi từ đó chặt nhị phân):

p2 p3 p5	Số	p2 p3 p5	Số	p2 p3 p5	Số
0 0 1	5	0 1 0	3	1 0 0	2
0 0 2	25	0 2 0	9	2 0 0	4
0 0 3	125	0 3 0	27	3 0 0	8
0 1 1	1 · 3 · 5 = 15	0 2 1	1 · 9 · 5 = 45	1 1 1	2 · 3 · 5 = 30

Em nhập $N$ (từ 1 đến 2000) rồi bấm Tiếp để xem mảng các số NUM5 đã sắp xếp và quá trình chặt nhị phân (lower_bound) tìm $N$:

N

Ví dụ nhanh:

Source code giải quyết theo tư tưởng mình đã trình bày ở trên và cũng đã nộp thành công trên web, các bạn xem để được hiểu rõ hơn:

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    const long long Max = 1e9;
    vector<int> a;
    for(int p2 = 0; ; ++p2){
        long long x = pow(2, p2);
        if(x > Max){
            break;
        }
        for(int p3 = 0; ; ++p3){
            long long y = pow(3, p3);
            if(x * y > Max){
                break;
            }
            for(int p5 = 0; ; ++p5){
                long long z = pow(5, p5);
                if(x * y * z > Max){
                    break;
                }
                a.push_back(x * y * z);
            }
        }
    }
    sort(a.begin(), a.end());
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        auto it = lower_bound(a.begin(), a.end(), n);
        if(*it != n){
            cout << "NO" << endl;
        }
        else{
            cout << "YES " << it - a.begin() + 1 << endl;
        }
    }
    return 0;
}

import sys
from bisect import bisect_left

def main():
    MAX = 10 ** 9
    a = []
    x = 1
    while x <= MAX:                   # x = 2^p2
        y = x
        while y <= MAX:               # y = 2^p2 * 3^p3
            z = y
            while z <= MAX:           # z = 2^p2 * 3^p3 * 5^p5
                a.append(z)
                z *= 5
            y *= 3
        x *= 2
    a.sort()
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    out = []
    for k in range(1, t + 1):
        n = int(data[k])
        pos = bisect_left(a, n)
        if pos < len(a) and a[pos] == n:
            out.append("YES " + str(pos + 1))
        else:
            out.append("NO")
    print("\n".join(out))

main()

Giải thích một số chỗ trong code:

1. Mảng a kiểu int là đủ vì mọi số đưa vào đều $\le 10^9$; còn các biến tích x, y, z và phép nhân x * y * z phải dùng long long, vì tích có thể vượt $10^9$ trước khi bị break.
2. *it luôn hợp lệ: số lớn nhất trong mảng là $2^9 \cdot 5^9 = 10^9$ đúng bằng giới hạn của $N$, nên lower_bound không bao giờ trả về a.end(). Bản Python mình vẫn kiểm tra thêm pos < len(a) cho chắc.
3. Đề gốc đọc/ghi file NUM5.INP / NUM5.OUT: nếu nộp ở kỳ thi thì các bạn thêm 2 dòng freopen("NUM5.INP", "r", stdin); và freopen("NUM5.OUT", "w", stdout); ở đầu hàm main. Trên HNOJ thì đọc/ghi chuẩn như code ở trên.

C++▶ Chạy tay từng dòng codeSinh 1530 số NUM5 ≤ 10^9 (gom bước cho gọn), sắp xếp, mỗi truy vấn lower_bound.

Dữ liệu vào (stdin) – sửa thoải mái4 1 10 7 44

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main() {

5 ios::sync_with_stdio(0);

6 cin.tie(0);

7 cout.tie(0);

8 const long long Max = 1e9;

9 vector<int> a;

10 for(int p2 = 0; ; ++p2){

11 long long x = pow(2, p2);

12 if(x > Max){

13 break;

14 }

15 for(int p3 = 0; ; ++p3){

16 long long y = pow(3, p3);

17 if(x * y > Max){

18 break;

19 }

20 for(int p5 = 0; ; ++p5){

21 long long z = pow(5, p5);

22 if(x * y * z > Max){

23 break;

24 }

25 a.push_back(x * y * z);

26 }

27 }

28 }

29 sort(a.begin(), a.end());

30 int t;

31 cin >> t;

32 while(t--){

33 int n;

34 cin >> n;

35 auto it = lower_bound(a.begin(), a.end(), n);

36 if(*it != n){

37 cout << "NO" << endl;

38 }

39 else{

40 cout << "YES " << it - a.begin() + 1 << endl;

41 }

42 }

43 return 0;

44}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(K)$ với $K = 1530$ số, rất nhỏ.
• Thời gian: sinh mảng $O(K)$, sắp xếp $O(K \log K)$, chỉ làm một lần. Mỗi truy vấn chặt nhị phân $O(\log K)$, khoảng 11 bước ⇒ tổng $O(K \log K + T \log K)$, cỡ $10^6$ phép tính, chạy tức thì.

Không gian$O(K)$

Thời gian$O(K \log K + T \log K)$

Một lưu ý nhỏ

Code của mình dùng endl sau mỗi dòng, lệnh này bắt chương trình đẩy dữ liệu ra ngay (flush) nên chậm hơn "\n". Với $10^5$ dòng thì vẫn ổn, nhưng các bạn nên quen dùng "\n" khi in nhiều dòng nhé.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 3300 giá trị $N$ (mọi $N$ từ 1 đến 3000 và 300 số ngẫu nhiên đến $2 \cdot 10^5$), so với code vét cạn chia thử cho 2, 3, 5 – khớp hết; các trường hợp biên $N = 10^9$ (YES 1530), $N = 999\,999\,999$ (NO) cũng đúng. Với $T = 10^5$, $N$ đến $10^9$: cách 1 bản C++ khoảng 0.2 giây, bản Python khoảng 23 giây; cách 2 cả C++ và Python đều dưới 0.2 giây.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇