Flowers (ICTU 56)

Nguồn: ICTU (problem 56) Độ khó: Trung bình Sàng Eratosthenes Số nguyên tố Cửa sổ trượt

Đề bài

Flowers

Điểm số: 1. Giới hạn thời gian: 1s. Giới hạn bộ nhớ: 512 MB. Người đăng: ICTU.

Đề bài: Có lẽ sau một thời gian rất dài chỉ ngồi coding, An cảm thấy thực sự căng thẳng và mệt mỏi. Vì vậy hôm nay An quyết định chọn ra một hoạt động mới giúp An cảm thấy thư giãn hơn. An ngồi đắn đo suy nghĩ. Các môn thể thao thì thực sự rất vui, nhưng mọi người cũng phải ở nhà hết rồi! Nếu chuyển qua chơi game, vậy cũng không khác nào ngồi coding với máy tính cả.

An quyết định chia sẻ những đắn đo này với Nam, và Nam gợi ý rằng: "Hay là làm vườn? Làm vườn tốt cho sức khỏe. Làm vườn ở ngoài trời, làn da tiếp xúc với ánh nắng có thể giúp có thể tăng cường Vitamin D. Làm vườn cũng giúp giảm huyết áp nè. Ngoài ra đây cũng là hoạt động nhẹ nhàng, giúp giảm căng thẳng rất hiệu quả!"

An thấy ý tưởng của Nam quả là tuyệt vời, vì vậy An đã quyết định tạo ra một vườn hoa của riêng mình. Vườn hoa mà An định trồng có dạng một hình chữ nhật có kích thước $n \times m$. Hình chữ nhật được chia thành các hàng và cột, với các hàng được đánh số từ 1 đến $n$ từ trên xuống dưới và các cột được đánh số từ 1 đến $m$ từ trái qua phải. Ô ở hàng thứ $r$ và cột thứ $c$ được thể hiện bởi cặp số $(r, c)$.

Là người yêu thích toán học, nên An muốn khu vườn của mình cũng có tính chất đặc biệt. An chỉ trồng hoa vào các ô $(r, c)$ nếu như $r + c$ là số nguyên tố.

Cho kích thước khu vườn của An, hãy giúp An tìm xem An cần phải trồng bao nhiêu bông hoa trong khu vườn nhé!

Đầu vào: Gồm một dòng duy nhất chứa hai số nguyên $n$ và $m$ $(1 \le n, m \le 10^7)$ là kích thước khu vườn.

Đầu ra: In ra một số nguyên duy nhất là số bông hoa mà An cần trồng.

Minh hoạ cho ví dụ hai ($n = 10$, $m = 7$): 26 ô được trồng hoa.

Ví dụ 1 – input

5 5

Ví dụ 1 – output

11

Ví dụ 2 – input

10 7

Ví dụ 2 – output

26

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 viết lại thành bài giải đầy đủ để các bạn tham khảo nhen. Hy vọng mang đến được giá trị cho các bạn 😇.

Giải thích ví dụ cho bạn nào chưa hiểu đề: hãy nhìn vào hình minh hoạ ví dụ 2, ma trận có 10 dòng, 7 cột, chỉ số dòng và cột tính từ 1. Ở dòng đầu tiên ($r = 1$), các giá trị $r + c$ sẽ là từ $2$ đến $8$; trong đó $2, 3, 5, 7$ là số nguyên tố nên các cột $1, 2, 4, 6$ được trồng hoa. Dòng thứ 2 có $r + c$ từ $3$ đến $9$, dòng tiếp theo từ $4$ đến $10$... Đếm hết cả 10 dòng được 26 bông hoa.

Với ví dụ 1 ($5 \times 5$), số bông hoa theo từng dòng lần lượt là $3, 3, 2, 2, 1$ ⇒ tổng 11.

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 1Duyệt từng ô, kiểm tra nguyên tố · TLECách 2Sàng + cửa sổ trượt · O(X log log X)

Cách 1Làm theo đề: duyệt từng ô – O(n · m · √(n + m))

Cách tự nhiên nhất: duyệt mọi ô $(r, c)$, kiểm tra $r + c$ có phải số nguyên tố không bằng cách thử chia cho các số từ $2$ đến $\sqrt{r + c}$, nếu đúng thì đếm thêm 1 bông hoa.

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;

bool isPrime(long long x){
    if(x < 2){
        return false;
    }
    for(long long i = 2; i * i <= x; ++i){
        if(x % i == 0){
            return false;
        }
    }
    return true;
}

int main(){
    long long n, m, cnt = 0;
    cin >> n >> m;
    for(long long r = 1; r <= n; ++r){
        for(long long c = 1; c <= m; ++c){
            if(isPrime(r + c)){
                cnt++;
            }
        }
    }
    cout << cnt;
    return 0;
}

def isPrime(x):
    if x < 2:
        return False
    i = 2
    while i * i <= x:
        if x % i == 0:
            return False
        i += 1
    return True

n, m = map(int, input().split())
cnt = 0
for r in range(1, n + 1):
    for c in range(1, m + 1):
        if isPrime(r + c):
            cnt += 1
print(cnt)

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

• Không gian: $O(1)$.
• Thời gian: có $n \cdot m$ ô, mỗi ô kiểm tra nguyên tố mất tới $O(\sqrt{n + m})$ ⇒ $O(n \cdot m \cdot \sqrt{n + m})$.

Không gian$O(1)$

Thời gian$O(n \cdot m \cdot \sqrt{n + m})$

Chắc chắn TLE

Riêng số ô đã là $n \cdot m$ lên tới $10^7 \cdot 10^7 = 10^{14}$, chưa kể kiểm tra nguyên tố. Mình đo thử thì chỉ với $n = m = 3000$ (9 triệu ô) C++ đã mất khoảng 0.4 giây, nên cách này chỉ dùng được với vườn rất nhỏ, kiểu để kiểm tra đáp án thôi nha.

Cách 2Sàng Eratosthenes + cửa sổ trượt – O(X log log X)

Bước 1: cần biết số nào là số nguyên tố

Hãy nhìn vào giới hạn của bài: $n, m$ tối đa có thể là $10^7$. Như thế $r + c$ tối đa có thể lên đến $2 \cdot 10^7$, còn tối thiểu thì tất nhiên là $2$ (vì $1 + 1 = 2$). Vậy ta có nhu cầu xét các số nguyên tố trong đoạn từ $2$ đến $n + m$, lớn nhất là khi $n = m = 10^7$, tức là xét từ $2$ đến 20 triệu.

Nếu dùng thuật toán kiểm tra từng số có phải số nguyên tố không thì độ phức tạp là $O(\sqrt{X})$ với $X$ là số cần kiểm tra. Giá trị lớn nhất $X = 2 \cdot 10^7$ thì $\sqrt{X} = \sqrt{20} \cdot \sqrt{10^6} \approx 4.47 \cdot 10^3$. Mà phải làm việc đó cho cả $2 \cdot 10^7$ số, tổng cộng $2 \cdot 10^7 \cdot 4.47 \cdot 10^3 \approx 9 \cdot 10^{10}$, coi như $10^{11}$ luôn rồi. Vượt xa giới hạn khoảng $10^8$ phép tính cho 1 giây ⇒ chắc chắn TLE.

Vậy ta phải dùng cách kiểm tra số nguyên tố tốt hơn cho toàn bộ các số từ $2$ đến $2 \cdot 10^7$, đó chính là sàng nguyên tố Eratosthenes. Các bạn có thể đọc lại bài viết về sàng trên VNOI Wiki: Lý thuyết số – phần 2.

Sàng Eratosthenes

Ban đầu coi mọi số từ $2$ đến $X$ là nguyên tố. Lần lượt xét $i = 2, 3, \ldots$ với $i \cdot i \le X$: nếu $i$ còn là nguyên tố thì gạch bỏ $i \cdot i,\ i \cdot i + i,\ i \cdot i + 2i, \ldots$ (bội của $i$). Sau sàng, isPrime[x] cho biết ngay $x$ có nguyên tố không trong $O(1)$.

Độ phức tạp của sàng là $O(X \log \log X)$. Với $X = 2 \cdot 10^7$ thì $\log_2 X \approx 24$, log thêm lần nữa chỉ còn cỡ $5$. Tóm lại khoảng $2 \cdot 10^7 \cdot 5 = 10^8$, vừa vặn giới hạn 1 giây.

Bước 2: đếm theo từng dòng bằng cửa sổ trượt

Có bảng sàng rồi nhưng nếu vẫn duyệt từng ô thì vẫn là $n \cdot m$ ô, vẫn TLE. Hãy nhìn lại các dòng cần kiểm tra:

• Dòng đầu tiên cần kiểm tra các giá trị từ $2$ đến $m + 1$.
• Dòng tiếp theo cần kiểm tra các giá trị từ $3$ đến $m + 2$.
• Dòng tiếp theo cần kiểm tra các giá trị từ $4$ đến $m + 3$.
• …
• Dòng cuối cùng cần kiểm tra các giá trị từ $n + 1$ đến $n + m$.

Ta chỉ cần đếm xem có bao nhiêu số nguyên tố trong đoạn $[2, m + 1]$ của dòng đầu tiên. Rồi đoạn $[3, m + 2]$ của dòng 2 tính ra chỉ là: loại bỏ 1 giá trị đầu của dòng trước (loại số $2$) và nhận thêm 1 giá trị mới phía sau (số $m + 2$). Đoạn $[4, m + 3]$ cũng vậy: loại số $3$, nhận thêm số $m + 3$. Giống hệt một cái cửa sổ độ dài $m$ trượt dần sang phải trên trục số.

Công thức cập nhật

Gọi sum1 là số bông hoa trên dòng hiện tại. Chuyển từ dòng $i - 1$ sang dòng $i$ (đoạn $[i + 1, i + m]$): nếu $i$ nguyên tố thì sum1--; nếu $m + i$ nguyên tố thì sum1++. Cộng sum1 của mọi dòng vào sum2 là đáp án.

Như thế chỉ phải duyệt hết dòng đầu tiên mất $O(m)$, sau đó lặp $n - 1$ lần còn lại, mỗi lần chỉ kiểm tra 2 giá trị đầu cuối bằng cách tra bảng sàng $O(1)$ ⇒ phần này chỉ $O(n + m)$.

Minh hoạ cửa sổ trượt

Em nhập $n$, $m$ rồi bấm Tiếp. Mỗi ô của vườn ghi giá trị $r + c$, ô xanh là số nguyên tố (có hoa). Bên dưới là trục số với cửa sổ (viền xanh dương) của dòng đang xét: ô đỏ gạch ngang là giá trị vừa bị loại, ô viền cam là giá trị vừa được nhận thêm.

n m

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này. Code này mình code vội đúng theo tư tưởng đã trình bày ở trên (đã nộp thành công trên web), mình chỉ căn lại thụt lề cho dễ đọc:

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, m;
    cin >> n >> m;
    vector<int> isPrime(n + m + 1);
    long long sz = n + m;
    for(int i = 0; i <= sz; ++i){
        isPrime[i] = true;
    }
    isPrime[0] = false;
    isPrime[1] = false;
    long long sum1 = 0;
    for(int i = 2; i * i <= sz; ++i){
        if(isPrime[i] == true){
            for(int j = i * i; j <= sz; j += i){
                isPrime[j] = false;
            }
        }
    }
    for(int i = 2; i <= m + 1; ++i){
        if(isPrime[i]){
            sum1++;
        }
    }
    long long sum2 = sum1;
    for(int i = 2; i <= n; ++i){
        if(isPrime[i]){
            sum1--;
        }
        if(isPrime[m + i]){
            sum1++;
        }
        sum2 += sum1;
    }
    cout << sum2;
    return 0;
}

n, m = map(int, input().split())
sz = n + m

# Sàng Eratosthenes trên đoạn 0..n+m
isPrime = bytearray([1]) * (sz + 1)
isPrime[0] = 0
isPrime[1] = 0
i = 2
while i * i <= sz:
    if isPrime[i]:
        # gạch bỏ i*i, i*i + i, ... (gán cả đoạn một lần cho nhanh)
        isPrime[i * i::i] = bytes(len(range(i * i, sz + 1, i)))
    i += 1

# Dòng 1: đếm số nguyên tố trong đoạn [2, m + 1]
sum1 = sum(isPrime[2:m + 2])
sum2 = sum1
# Dòng i: bỏ giá trị i (đầu dòng trước), thêm giá trị m + i
for i in range(2, n + 1):
    sum1 += isPrime[m + i] - isPrime[i]
    sum2 += sum1
print(sum2)

C++▶ Chạy tay từng dòng codeSàng Eratosthenes trên 0..n + m, đếm dòng 1 rồi trượt cửa sổ cho các dòng sau.

Dữ liệu vào (stdin) – sửa thoải mái5 5

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 long long n, m;

9 cin >> n >> m;

10 vector<int> isPrime(n + m + 1);

11 long long sz = n + m;

12 for(int i = 0; i <= sz; ++i){

13 isPrime[i] = true;

14 }

15 isPrime[0] = false;

16 isPrime[1] = false;

17 long long sum1 = 0;

18 for(int i = 2; i * i <= sz; ++i){

19 if(isPrime[i] == true){

20 for(int j = i * i; j <= sz; j += i){

21 isPrime[j] = false;

22 }

23 }

24 }

25 for(int i = 2; i <= m + 1; ++i){

26 if(isPrime[i]){

27 sum1++;

28 }

29 }

30 long long sum2 = sum1;

31 for(int i = 2; i <= n; ++i){

32 if(isPrime[i]){

33 sum1--;

34 }

35 if(isPrime[m + i]){

36 sum1++;

37 }

38 sum2 += sum1;

39 }

40 cout << sum2;

41 return 0;

42}

ChậmVừaNhanhRất nhanh

Một vài ghi chú về code:

• vector<int> isPrime(n + m + 1) có tối đa $2 \cdot 10^7 + 1$ phần tử int, tốn khoảng 80 MB, vẫn nằm thoải mái trong giới hạn 512 MB của đề. Nếu đề chặt bộ nhớ hơn thì đổi sang vector<bool> hoặc vector<char>.
• Vòng sàng dùng int i với điều kiện i * i <= sz: $i$ chỉ lên tới khoảng $4473$ nên i * i không tràn int; j bắt đầu từ i * i tối đa $2 \cdot 10^7$, cũng an toàn.
• Đáp án có thể lên tới cỡ $n \cdot m = 10^{14}$ (thực tế với $n = m = 10^7$ là $6\,254\,632\,112\,109$), nên sum2 bắt buộc là long long.
• Bản Python dùng bytearray và gán cả đoạn isPrime[i * i::i] = ... để sàng nhanh, thay cho vòng lặp từng phần tử.

Đánh giá độ phức tạp của cách làm này (đặt $X = n + m$):

• Không gian: mảng sàng $X + 1$ phần tử ⇒ $O(X)$.
• Thời gian: sàng mất $O(X \log \log X)$, đếm dòng đầu $O(m)$, trượt cửa sổ $O(n)$. Lấy cái lớn nhất ⇒ $O(X \log \log X)$, dễ dàng AC trong 1 giây.

Không gian$O(n + m)$

Thời gian$O((n + m) \log \log (n + m))$

Lưu ý với bản Python

Với $n = m = 10^7$, bản Python ở trên mình đo mất khoảng 2.9 giây (vòng trượt $10^7$ lần trong Python khá chậm), còn C++ chỉ khoảng 0.5 giây. Hệ thống chấm thường cho Python thêm thời gian, nhưng nếu bị TLE thì các bạn nộp bản C++ nhé.

Ghi chú của mình: code C++ và Python của cả 2 cách cho đúng output 2 ví dụ của đề, và đã được kiểm tra với 400 bộ test ngẫu nhiên ($n, m \le 40$), so với code vét cạn đếm từng ô – khớp hết. Ngoài ra $n = 1, m = 10^7$ và $n = 10^7, m = 1$ đều ra $664\,579$ (đúng bằng số số nguyên tố không vượt quá $10^7$). Với $n = m = 10^7$: cách 2 C++ chạy khoảng 0.5 giây, Python khoảng 2.9 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 😇