# Lời giải VOI 22 Bài 6 - Xây dựng ma trận

:::info
> **Người làm**: Trần Thiên Phúc - 12Ti - K28, THPT Chuyên Hùng Vương, Thành phố Hồ Chí Minh.
> **Nội dung**:
> [TOC]

> Link đề và chỗ chấm thử: [VNOJ](https://oj.vnoi.info/problem/voi22_matrix).

> Tài liệu tham khảo: [Lời giải của anh Phạm Văn Hạnh](https://www.youtube.com/live/UukxDzcLEl0?si=aGM_CFjD4YdXTdyJ).
:::
:::danger
**Note: bài viết vẫn còn đang được cập nhập, hiện tại lời giải chỉ mới tới subtask 2**.
:::

---
## Đề bài
Cho hai số $n$ và $m$, tìm bảng có kích thước $n \times m$ thỏa mãn:
* Với mỗi ô $a[i][j]$:
* $\forall \gcd(y, j) = 1: a[i][y] \neq a[i][j]$
* $\forall \gcd(x, i) = 1: a[x][j] \neq a[i][j]$
* Thứ tự từ điển nhỏ nhất.

In ra $\sum a[i][j] \mod {10}^{9} + 7$.
:::warning
**Lưu ý**: để tiện xử lí thì mình sẽ gọi $n$ là số hàng và $m$ là số cột, khác với đề bài gốc ($m$ là số hàng và $n$ là số cột).
:::

---
## Subtask 1: $n \times m \leq {10}^4$
### Hướng dẫn
Ta tìm trực tiếp mảng a thỏa mãn yêu cầu đề bài.

Khởi tạo: $a[1][1] = 1$.

Ta duyệt các ô theo thứ tự từng hàng và tới từng cột, với mỗi ô $a[i][j]$, lưu thêm một mảng $vis[num]$ để kiểm tra xem $num$ đã xuất hiện trong các ô thỏa mãn điều kiện đề bài mà $a[i][j]$ phải khác. Như vậy $a[i][j]$ là $\texttt{mex}$ (số đầu tiên $\geq 1$ không xuất hiện) của các số đó.

::: info
:::spoiler **Giải thích**
> Do yêu cầu về thứ tự từ điển min: tất cả vị trí ở hàng bé hơn và các cột bé hơn cùng hàng phải đạt cấu hình min, nếu không thỏa điều kiện này thì cấu hình hiện tại cho dù chọn như thế nào cũng không đảm bảo là min.

> Với cấu hình trước đó min thì ta cũng cần chọn cấu hình $a[i][j]$ min.
:::

### Code
::: success
::: spoiler **Code**

a[1][1] = 1;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        if (i == 1 and j == 1) continue;

        // Thêm các giá trị vào trong mảng vis
        for (int x = 1; x < i; x++) {
            if (__gcd(x, i) == 1) {
                vis[a[x][j]] = true;
            }
        }
        for (int y = 1; y < j; y++) {
            if (__gcd(y, j) == 1) {
                vis[a[i][y]] = true;
            }
        }

        int mex = 1;
        while (vis[mex]) mex++;
        a[i][j] = mex;

        // Loại bỏ các giá trị vừa thêm ra khỏi vis để cho mảng vis rỗng ở lần duyệt ô a[i][j] sau.
        for (int x = 1; x < i; x++) {
            if (__gcd(x, i) == 1) {
                vis[a[x][j]] = false;
            }
        }
        for (int y = 1; y < j; y++) {
            if (__gcd(y, j) == 1) {
                vis[a[i][y]] = false;
            }
        }
    }
}

int res = 0;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        add(res, a[i][j]); // cộng a[i][j] vào res và lấy mod cho res
    }
}

cout << res;

:::

---
:::warning
**Lưu ý**: Từ subtask 2 trở đi, mình sẽ trình bày cách làm có hơi khuynh hướng tà đạo, mình sẽ không giải một cách trực tiếp mà sử dụng một số kĩ thuật / mẹo để tìm ra cách giải.
:::

---
## Subtask 2: $n = 1, m \leq {10}^9$
### Hướng dẫn
Ở đây ta sẽ dùng một mẹo **tìm quy luật**:
::: info
:::spoiler **Mẹo tìm quy luật tổng quát**
> Trích từ anh Phạm Văn Hạnh:
> Với các bài tập mà input chỉ gồm 1 hoặc 2 số thì ta có thể sử dụng phương pháp mò:
> - Bước 1: Bằng mọi cách, tìm ra kết quả của những chỉ số $m$ và $n$ nhỏ ($m, n \leq 10$ hoặc $20$...). Ta có thể tính bằng tay, máy tính Fx500MS Casio, tính bằng excel hoặc code duyệt vét cạn... để tìm ra kết quả của những trường hợp $m$ và $n$ nhỏ.
> - Bước 2: Quan sát kết quả vừa tính được và cố gắng mò ra quy luật.
> Một khi đã mò thì không có gì đảm bảo là sẽ tìm ra quy luật. Và đã là mò thì không có cách cụ thể nào để mò cả. Nhưng trong nhiều trường hợp, việc mò là cách tốt nhất để tìm ra quy luật và thuật toán.
:::
#### Bước 1: Tìm quy luật
<details style="border-left: 4px solid #0af; padding: 8px; border-radius: 6px;">
<summary><b>Hướng dẫn cách tìm quy luật cho bài</b></summary>

Bằng cảm giác, việc tìm quy luật của tổng $S$ sẽ khó (do nó có modulo) nên ta có thể thử tìm kiếm quy luật của bảng.

Ta sẽ thử với $m = 30$, sử dụng code subtask 1 đã làm đúng để thử, ta sẽ in ra các giá trị của từng vị trí để xem.
::: success
::: spoiler **Code in dãy 1**

for (int j = 1; j <= m; j++) cerr << j << ": " << a[1][j] << "\n";

:::
Ta có được dãy như sau:
::: success
::: spoiler **Dãy 1**

1: 1
2: 2
3: 3
4: 2
5: 4
6: 2
7: 5
8: 2
9: 3
10: 2
11: 6
12: 2
13: 7
14: 2
15: 3
16: 2
17: 8
18: 2
19: 9
20: 2
21: 3
22: 2
23: 10
24: 2
25: 4
26: 2
27: 3
28: 2
29: 11
30: 2

:::
Bằng trực quan, ta có thể thấy được số ở vị trí $1$ có giá trị là $1$, và số ở vị trí chẵn sẽ có giá trị là $2$, còn các giá trị còn lại $3, 4,...$ xuất hiện ở đâu thì chưa rõ.

Lần này ta sẽ thử theo kiểu giá trị xuất hiện ở những vị trí nào để xem thử.
::: success
::: spoiler **Code in dãy 2**

vector <int> pos[105];
for (int j = 1; j <= m; j++) pos[a[1][j]].push_back(j);
for (int id = 1; id <= 30; id++) {
    cerr << id << ": ";
    for (int j: pos[id]) cerr << j << " ";
    cerr << "\n";
}

:::
Ta có được dãy như sau:
::: success
::: spoiler **Dãy 2**

1: 1
2: 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30
3: 3 9 15 21 27
4: 5 25
5: 7
6: 11
7: 13
8: 17
9: 19
10: 23
11: 29
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:

:::
Lần này ta có thể thấy được các giá trị số nguyên tố lần lượt xuất hiện ở vị trí $2, 3, 4, 5, ...$ với các giá trị lần lượt là $2, 3, 5, 7, ...$.
Trên cùng một hàng, các số theo sau số nguyên tố đầu tiên đều là những số chia hết cho số nguyên tố đó.
</details>

Nếu để ý kĩ ta có thể nhận ra quy luật của bảng như sau:
::: success
**Quy luật:**
$a[1][1] = 1$.
Với các vị trí $\geq 1:$
Ta liệt kê các số nguyên tố bắt đầu từ số thứ tự là $1$:
- Số nguyên tố thứ $1$ là $2$,
- Số nguyên tố thứ $2$ là $3$,
- Số nguyên tố thứ $3$ là $5$,
$...$,
- Số nguyên tố thứ $i$ là $p$.

Gọi $primeId(p) = i$: số thứ tự nguyên tố của $p$ là $i$.

* Với vị trí **$p$ là số nguyên tố**, giá trị của ô là $i + 1$.
* Ngược lại, vị trí **$p$ không phải là số nguyên tố**, giá trị của ô là $primeId($thừa số nguyên tố nhỏ nhất của $p) + 1$.
:::spoiler **Ví dụ**
Vị trí $7$ có giá trị là $5$, do $7$ là số nguyên tố thứ $4$, giá trị $= 4 + 1 = 5$.
Vị trí $6$ có giá trị là $2$, do $6 = 2^1 \times 3^1 \rightarrow$ thừa số nguyên tố nhỏ nhất là $2$, và $2$ là số nguyên tố thứ $1$, giá trị $= 1 + 1 = 2$.
:::

Khi đã có được quy luật, ta có bài toán con khác: tìm tổng của bảng.
Do là $m$ lớn nên ta có thể sử dụng mẹo **sinh mảng hằng** để rút ngắn thời gian chạy.
::: info
:::spoiler **Cụ thể về kĩ thuật sinh mảng hằng**
> Ta sẽ sinh ra một mảng gồm các số đáp án sẵn để rút ngắn quá trình tính toán, trong quá trình làm thì các số trong mảng hằng sẽ không bị thay đổi.
> Cú pháp thường thấy là:
> ```cpp=
> const int res[size] = {num_1, num_2, ...};
> ```
:::

#### Bước 2: Sinh mảng hằng
<details style="border-left: 4px solid #0af; padding: 8px; border-radius: 6px;">
<summary><b>Nhận xét để nghĩ ra việc sinh mảng hằng cho bài</b></summary>

Tất nhiên ta sẽ không tìm hết một lượt ${10}^9$ đáp án từ $1$ tới ${10}^9$ được vì giới hạn bộ nhớ.
Nhận thấy: Với mỗi số ta cần quan tâm các điều:

1. Số đó có phải số nguyên tố hay không? $\rightarrow$ có thể làm với sàng nguyên tố trên đoạn có độ dài an toàn khoảng $\leq {10}^6$.

2. Nếu phải thì cái $id$ của nó là bao nhiêu? $\rightarrow$ cần biết được **số lượng số nguyên tố** trước đó.

3. Nếu không thì cái giá trị của thừa số nguyên tố nhỏ nhất là bao nhiêu? $\rightarrow$ có thể thực hiện truy vấn thừa số nguyên tố nhỏ nhất trong quá trình sàng nguyên tố.

Từ các nhận xét trên, ta sẽ sinh mảng hằng với các đáp án có vị trí $m \mid {10}^6$ như: ${10}^6, 2 \times {10}^6, ...$
</details>

::: success
**Ta cần làm hai mảng hằng**:
$numPrime[x]:$ Số lượng số nguyên tố $\leq x$.
$sum[x]: \sum_{j = 1}^{x} a[1][j] \mod {10}^{9} + 7$.
:::

Tới đây ta có thể code sàng nguyên tố để sinh mảng hằng.
::: success
::: spoiler **Code sinh mảng hằng**

// TranThienPhuc2657
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int SQRT = 31622; // căn(10^9)
const int N = 1e6;

bool isPrime[SQRT + 5];
int Prime[N + 5];
int numP = 0, S = 0;
vector <int> numPrime, sum;

void add(int &x, int y) {
    x += y;
    if (x >= mod) x -= mod;
}

void eratosthenes() { // trong quá trình sinh mảng hằng, ta cần biết được rằng các số <= căn(10^9) có phải số nguyên tố hay không
    for (int i = 2; i <= SQRT; i++) isPrime[i] = true;
    for (int i = 2; i * i <= SQRT; i++) if (isPrime[i]) {
        for (int j = i * i; j <= SQRT; j += i) isPrime[j] = false;
    }
}

void cal(int l, int r) { // sàng nguyên tố trên đoạn
    // Quy định: Prime[i] = 1 => i là số nguyên tố
    // Prime[i] != 1 => Prime[i] là giá trị idPrime(thừa số nguyên tố nhỏ nhất của i) + 1
    for (int i = 0; i <= r - l; i++) Prime[i] = 1;

    int idPrime = 0;
    for (int i = 2; i * i <= r; i++) if (isPrime[i]) {
        idPrime++;
        for (int j = max(i * i, ((l - 1) / i + 1) * i); j <= r; j += i) if (Prime[j - l] == 1) {
            Prime[j - l] = idPrime + 1;
        }
    }

    for (int j = l; j <= r; j++) {
        if (j == 1) { // a[1][1] = 1
            add(S, 1);
        }
        else {
            if (Prime[j - l] == 1) { // j là số nguyên tố => xử lí ở đây
                numP++;
                add(S, numP + 1);
            }
            else { // j không phải số nguyên tố => đã tiền xử lí ở trên
                add(S, Prime[j - l]);
            }
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    eratosthenes();
    // ta chia thành 1000 đoạn, mỗi đoạn gồm 10^6 phần tử
    for (int i = 1; i <= 1000; i++) {
        int l = (i - 1) * N + 1, r = i * N;
        cal(l, r);
        numPrime.push_back(numP);
        sum.push_back(S);
    }

    // in hai mảng ra.
    ofstream cout;
    cout.open("numPrime.txt");
    for (int i: numPrime) cout << i << ", ";
    cout.close();

    cout.open("sum.txt");
    for (int i: sum) cout << i << ", ";
    cout.close();
    return 0;
}

:::
Code trên chạy trong khoảng 10s, không tốn quá nhiều thời gian để in ra.
Ta sao chép hai dãy số và cho vào mảng hằng.
Khi có mảng hằng, ta còn phần dư ra có độ dài khoảng ${10}^6$, khi này ta có thể giữ lại code sàng nguyên tố trên đoạn như trên để tính tiếp cho phần đó.
### Code
::: success
::: spoiler **Code**

// TranThienPhuc2657
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int SQRT = 31622;
const int N = 1e6;
const int numPrime[1000] = {}; // Các số trong mảng hằng cần được điền vào
const int sum[1000] = {};

int n, m;
bool isPrime[SQRT + 5];
int Prime[N + 5];
int numP = 0, S = 0;

void add(int &x, int y) {
    x += y;
    if (x >= mod) x -= mod;
}

void eratosthenes() { // trong quá trình tính, ta cần biết được rằng các số <= căn(10^9) có phải số nguyên tố hay không
    for (int i = 2; i <= SQRT; i++) isPrime[i] = true;
    for (int i = 2; i * i <= SQRT; i++) if (isPrime[i]) {
        for (int j = i * i; j <= SQRT; j += i) isPrime[j] = false;
    }
}

void cal(int l, int r) { // sàng nguyên tố trên đoạn
    // Quy định: Prime[i] = 1 => i là số nguyên tố
    // Prime[i] != 1 => Prime[i] là giá trị idPrime(thừa số nguyên tố nhỏ nhất của i) + 1
    for (int i = 0; i <= r - l; i++) Prime[i] = 1;

    int idPrime = 0;
    for (int i = 2; i * i <= r; i++) if (isPrime[i]) {
        idPrime++;
        for (int j = max(i * i, ((l - 1) / i + 1) * i); j <= r; j += i) if (Prime[j - l] == 1) {
            Prime[j - l] = idPrime + 1;
        }
    }

    for (int j = l; j <= r; j++) {
        if (j == 1) { // a[1][1] = 1
            add(S, 1);
        }
        else {
            if (Prime[j - l] == 1) { // j là số nguyên tố => xử lí ở đây
                numP++;
                add(S, numP + 1);
            }
            else { // j không phải số nguyên tố => đã tiền xử lí ở trên
                add(S, Prime[j - l]);
            }
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    freopen("MATRIX.inp", "r", stdin);
    freopen("MATRIX.out", "w", stdout);

    cin >> n >> m;

    eratosthenes();
    // truy xuất đáp án đã tính sẵn từ mảng hằng
    int id = m / N;
    if (id > 0) {
        numP = numPrime[id - 1];
        S = sum[id - 1];
    }
    int l = id * N + 1, r = m;
    cal(l, r);
    cout << S;
    return 0;
}

:::

---
## Tổng hợp code
:::info
Các bạn bấm vào các link ở cột "**Code**" để xem các code tham khảo.
:::
| **Subtask** | **Ràng buộc** | **Độ phức tạp** | **Code** |
|:-----------:|:------------------------:|:-------------------------------------------------:|:------------------------------------------------------------------------------------:|
| 1 | $n \times m \leq {10}^4$ | $\mathcal{O}(n \times m \times \max(n, m))$ | [Code chính](https://ideone.com/cwZuZT) |
| 2 | $n = 1, m \leq {10}^9$ | $\mathcal{O}(R \log \log R),$ $R = m \mod {10}^6$ | [Sinh mảng hằng](https://ideone.com/yIAXMk), [Code chính](https://ideone.com/h2RrOU) |
| 3 | $n, m \leq {10}^6$ | $\mathcal{O}()$ | |
| 4 | $n, m \leq {10}^9$ | $\mathcal{O}()$ | |

---
## Tổng hợp các kĩ thuật / mẹo được sử dụng
- Tìm kiếm quy luật $\rightarrow$ với các bài có một hay hai hằng số nhỏ.
- Sinh mảng hằng $\rightarrow$ các bài cần chuẩn bị trước đáp án để có thể xử lí nhanh hơn
- Sàng nguyên tố Eratosthenes

---
## Lời nói cuối
Bài này là một bài có thể hoàn toàn giải bằng toán. Nhưng việc chứng minh sẽ rất khó khăn. Thay vì vậy ta có thể sử dụng các kĩ thuật / mẹo làm bài để có thể đơn giản hóa được bài toán một phần, đặc biệt là trong không khí phòng thi đầy áp lực.