Elearning CodePath – CTP Online Judge

Bảng Nguyên Tố

MPRIME

🟢 Easy #General #Math #Optimization

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho một bảng các số nguyên dương $A$ có kích thước $N \times M$ ($1 \le N, M \le 500$).

**Thao tác:** Chọn một số bất kỳ trong bảng và tăng giá trị của số đó lên $1$. Một số có thể được chọn thực hiện thao tác nhiều lần.

**Bảng có tính nguyên tố:** Một bảng thỏa mãn một trong hai điều kiện sau:
1.  Tồn tại một **hàng** bất kỳ mà tất cả các số trong hàng đều là **số nguyên tố**.
2.  Tồn tại một **cột** bất kỳ mà tất cả các số trong cột đều là **số nguyên tố**.

Yêu cầu: Tìm **số thao tác biến đổi ít nhất** để bảng ban đầu trở thành bảng có tính nguyên tố.

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `MPRIME.INP`:

* Dòng 1: Gồm 2 số $N, M$ tương ứng là số dòng và số cột của bảng.
* $N$ dòng sau: Mỗi dòng gồm $M$ số nguyên dương có giá trị $\le 10^6$ là các số trong bảng ban đầu. Các số trên một dòng cách nhau một dấu cách.

Giới hạn:
* $1 \le N, M \le 500$.
* Giá trị phần tử $\le 10^6$.

---
### 📤 Định dạng Đầu ra

Ghi ra file `MPRIME.OUT` một số duy nhất là số thao tác ít nhất cần biến đổi.

---
### ✨ Ví dụ

| Input (`MPRIME.INP`) | Output (`MPRIME.OUT`) |
| :--- | :--- |
| `3 3` <br> `1 2 3` <br> `4 9 8` <br> `2 3 9` | `1` |

Giải thích:
* **Hàng 1:** $\{1, 2, 3\}$. Để $1 \to 2$ (nguyên tố) cần 1 thao tác. Tổng thao tác: $1 + 0 + 0 = 1$.
* **Cột 2:** $\{2, 9, 3\}$. Để $9 \to 11$ (nguyên tố) cần $11 - 9 = 2$ thao tác.
* **Cột 3:** $\{3, 8, 9\}$. Để $8 \to 11$ cần 3 thao tác; $9 \to 11$ cần 2 thao tác. Tổng: $0 + 3 + 2 = 5$.

Số thao tác ít nhất là $1$ (chọn hàng 1, tăng $1 \to 2$).

---
### 🏷 Ràng buộc

| Tỷ lệ điểm | Ràng buộc |
| :--- | :--- |
| $50\%$ | $N \le 50$ |
| $50\%$ | $1 \le N, M \le 500$ (Ràng buộc chung) |

---

✅ Đã AC: 1 / 1 submissions

📘 Lời giải

### Bảng Nguyên Tố

#### Giải thích Phương pháp Tối ưu (Sàng Eratosthenes và Tiền xử lý Chi phí - Code full)

**Tại sao Sàng Eratosthenes* là bắt buộc (ngay cả với $N$ nhỏ):

* Dù $N$ nhỏ ($N \le 50$)*, giá trị phần tử $A_{ij}$ vẫn lên tới $V_{max} = 10^6$. Nếu dùng *Trial Division* (phép chia thử) để kiểm tra nguyên tố cho mỗi phần tử thì độ phức tạp cho mỗi phần tử là $O(\sqrt{V_{max}}) \approx O(1000)$.

-> Tổng độ phức tạp sẽ là $O(N \cdot M \cdot \sqrt{V_{max}}) \le O(500 \cdot 500 \cdot 1000) = 250$ triệu phép tính. Con số này là cao và có nguy cơ **TLE** (Time Limit Exceeded).

**Ý tưởng cốt lõi:*

* Sử dụng Sàng Eratosthenes để tiền xử lý chi phí biến đổi $\text{Cost}[x]$ cho mọi số $x \le 10^6$ trong thời gian $O(V_{max}  \log V_{max})$ và sau đó quét bảng $A$ trong thời gian $O(N \cdot M)$.

### I. Tiền xử lý Chi phí Biến đổi: Trước khi duyệt bảng, ta cần xác định chi phí tối thiểu để biến một số $x$ thành số nguyên tố $y \ge x$.

**Sàng Eratosthenes:* Tiền xử lý tất cả các số nguyên tố lên đến $V_{max} = 10^6$.

**Tính mảng Chi phí ($Cost$)*:

* Duyệt ngược từ $V_{max}$ về $1$ để tính chi phí $\text{Cost}[x]$. $\text{Cost}[x]$ là số thao tác $t = y - x$, trong đó $y$ là số nguyên tố nhỏ nhất sao cho $y \ge x$.

$\text{Cost}[x] = \left( \min \{y \mid y \ge x \text{ và } y \text{ là số nguyên tố}\} \right) - x$

### II. Tính toán kết quả tối thiểu $\min(M_1, M_2)$

*a) Tính chi phí tối thiểu trên các hàng ($M_1$)*

* Duyệt qua từng hàng $i \in [1, N]$. Với mỗi phần tử $A_{ij}$ trong hàng $i$, ta tra cứu chi phí $\text{Cost}[A_{ij}]$ trong $O(1)$.

Gọi $S_i$ là tổng số thao tác biến đổi trên hàng $i$:

$S_i = \sum_{j=1}^{M} \text{Cost}[A_{ij}]$

Số thao tác biến đổi ít nhất trên các hàng là $M_1$:$M_1 = \min_{i=1}^{N} S_i$

*b) Tính chi phí tối thiểu trên các cột ($M_2$)*

Tương tự, duyệt qua từng cột $j \in [1, M]$.Gọi $C_j$ là tổng số thao tác biến đổi trên cột $j$:$C_j = \sum_{i=1}^{N} \text{Cost}[A_{ij}]$

Số thao tác biến đổi ít nhất trên các cột là $M_2$:

$M_2 = \min_{j=1}^{M} C_j$

*c) Kết quả*

Kết quả bài toán là chi phí tối thiểu để thỏa mãn điều kiện bảng có tính nguyên tố (một hàng $\text{HOẶC}$ một cột là nguyên tố):

$\text{Kết Quả} = \min(M_1, M_2)$

### III. Code (Tối ưu hóa Tiền xử lý Chi phí)
```
#include <bits/stdc++.h>

using namespace std;

// Giới hạn giá trị lớn nhất của phần tử (Vmax)
// Sàng cần chạy đến số nguyên tố lớn nhất gần 10^6
const int MAX_VAL = 1000000;
const int SIEVE_LIMIT = 1000005;

// Mảng Sàng: is_prime[i] = true nếu i là số nguyên tố
vector<bool> is_prime(SIEVE_LIMIT, true);

// Mảng lưu chi phí biến đổi: Cost[x] = P - x, với P là số nguyên tố nhỏ nhất >= x
vector<int> cost_to_prime(SIEVE_LIMIT);

// Bước 1: Sàng Eratosthenes (O(V log log V))
void sieve() {
    is_prime[0] = is_prime[1] = false;
    for (int p = 2; p * p < SIEVE_LIMIT; p++) {
        if (is_prime[p]) {
            for (int i = p * p; i < SIEVE_LIMIT; i += p)
                is_prime[i] = false;
        }
    }
}

// Bước 2: Tiền xử lý mảng chi phí (Cost Array) (O(V))
void precompute_cost() {
    // next_p lưu số nguyên tố nhỏ nhất >= i đã tìm thấy
    int next_p = SIEVE_LIMIT; 
    for (int i = SIEVE_LIMIT - 1; i >= 1; --i) {
        if (is_prime[i]) {
            // Nếu i là nguyên tố, chi phí biến đổi là 0
            cost_to_prime[i] = 0;
            next_p = i; // Cập nhật số nguyên tố gần nhất
        } else {
            // Nếu i không nguyên tố, chi phí là khoảng cách đến số nguyên tố gần nhất (next_p)
            cost_to_prime[i] = next_p - i;
        }
    }
}

void solve() {
    // 1. Tiền xử lý Sàng và Chi phí 
    sieve();
    precompute_cost();

int N, M;
    if (!(cin >> N >> M)) return;

// Đọc bảng A và tính chi phí hàng/cột (O(N*M))
    vector<vector<int>> A(N, vector<int>(M));
    // Dùng long long cho tổng chi phí vì N*M*Vmax có thể lớn
    vector<long long> row_cost(N, 0); 
    vector<long long> col_cost(M, 0);

// Biến lưu kết quả tối thiểu, khởi tạo với giá trị lớn nhất có thể
    long long min_ops = LLONG_MAX;

// Đọc input và tính tổng chi phí cho từng hàng/cột
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> A[i][j];
            
            // Chi phí biến A[i][j] thành số nguyên tố >= A[i][j] (O(1) tra cứu)
            int cost = cost_to_prime[A[i][j]]; 
            
            // Cập nhật tổng chi phí hàng và cột
            row_cost[i] += cost; // Tổng Si (cho hàng i)
            col_cost[j] += cost; // Tổng Cj (cho cột j)
        }
    }

// 2. Tìm chi phí tối thiểu cho hàng (M1 = min(Si)) (O(N))
    for (int i = 0; i < N; ++i) {
        min_ops = min(min_ops, row_cost[i]);
    }

// 3. Tìm chi phí tối thiểu cho cột (M2 = min(Cj)) (O(M))
    for (int j = 0; j < M; ++j) {
        min_ops = min(min_ops, col_cost[j]);
    }
    
    // Kết quả cuối cùng là min(M1, M2)

// Ghi ra kết quả
    cout << min_ops << endl;
}

int main() {
    // Tối ưu hóa I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}
```