Elearning CodePath – CTP Online Judge

Số Chia và Bảng

DIVISORS_IN_MULTIPLI

🟢 Easy #Hash #Math

### 📌 Thông tin chung

| Mục | Chi tiết |
| :--- | :--- |
| **Tên File Input** | `Divisors.inp` |
| **Tên File Output** | `Divisors.out` |
| **Độ phức tạp mong muốn** | $O(T \cdot \sqrt{M} \cdot \log N)$ |

---

### 📝 Bài toán

Cho một bảng cửu chương $A$ kích thước $N \times N$, với phần tử tại vị trí $(i, j)$ là $A_{i,j} = i \cdot j$ ($1 \le i, j \le N$).
Cho số nguyên dương $M = M_1 \cdot M_2$.

Yêu cầu: Với mỗi **ước số** $d$ của $M$:
1.  Kiểm tra xem $d$ có xuất hiện trong bảng $A$ hay không (tức là $\exists i, j \in [1, N]$ sao cho $i \cdot j = d$).
2.  Nếu $d$ xuất hiện, tìm **chỉ số hàng nhỏ nhất** $r_{\min}$ ($1 \le r_{\min} \le N$) sao cho tồn tại $j \in [1, N]$ với $r_{\min} \cdot j = d$.

Đặt $D = \{d_1, d_2, \dots, d_K\}$ là tập hợp tất cả các ước số của $M$, sắp xếp theo thứ tự tăng dần.
Đặt $A = \{a_1, a_2, \dots, a_K\}$ là mảng câu trả lời, trong đó:
$$
a_i = \begin{cases}
r_{\min}(d_i) & \text{nếu } d_i \text{ xuất hiện trong bảng } A \\
0 & \text{ngược lại}
\end{cases}
$$

**Đầu ra:**
1.  Số nguyên $S$: Số lượng ước số $d_i$ của $M$ có mặt trong bảng $A$ ($S = \text{số lượng } a_i \ne 0$).
2.  Giá trị $X$: Phép toán XOR theo bit của tất cả các phần tử trong mảng câu trả lời $A$:
$$
X = a_1 \oplus a_2 \oplus \dots \oplus a_K
$$
(Trong đó $\oplus$ là phép XOR theo bit).

---

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

Dữ liệu vào gồm nhiều bộ test.

* **Dòng 1:** Số nguyên dương $T$ ($1 \le T \le 10$) – số lượng bộ test.
* **$T$ khối dòng tiếp theo:** Mỗi khối mô tả một bộ test:
    * Dòng đầu tiên chứa ba số nguyên $N, M_1, M_2$ – kích thước bảng và hai thừa số của $M$.

**Giới hạn (Ràng buộc):**
$$
\begin{array}{l}
1 \le N \le 10^9 \\
1 \le M_1, M_2 \le 10^9 \\
M = M_1 \cdot M_2 \le 10^{18}
\end{array}
$$
(Lưu ý: $M$ có thể đạt đến $10^{18}$, cần dùng kiểu dữ liệu 64-bit integer, $\text{long long}$ trong C++).

---

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

Với mỗi bộ test, in ra hai dòng:
1.  Dòng đầu tiên: Số nguyên $S$ – số ước số của $M$ có mặt trong bảng $N \times N$.
2.  Dòng thứ hai: Giá trị $X$ – phép XOR của tất cả các phần tử trong mảng câu trả lời $A$.

---

### ✨ Ví dụ

| Input (`Divisors.inp`) | Output (`Divisors.out`) |
| :--- | :--- |
| `3` `3 72 1` `10 10 15` `6 1 210` | `6` `2` `10` `0` `8` `5` |

---

### 🧪 Giải thích Ví dụ (Test 1)

* $N=3$, $M = 72 \cdot 1 = 72$.
* Bảng $3 \times 3$:
$$
\begin{pmatrix}
1 & 2 & 3 \\
2 & 4 & 6 \\
3 & 6 & 9
\end{pmatrix}
$$
* Các ước số của $M=72$ (tăng dần): $D = [1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72]$. (Tổng cộng $K=12$ ước).

| $d_i$ | Xuất hiện? | $r_{\min}(d_i)$ | $a_i$ |
| :--- | :--- | :--- | :--- |
| 1 | Có ($1 \cdot 1$) | $r=1$ | 1 |
| 2 | Có ($1 \cdot 2, 2 \cdot 1$) | $r=1$ | 1 |
| 3 | Có ($1 \cdot 3, 3 \cdot 1$) | $r=1$ | 1 |
| 4 | Có ($2 \cdot 2$) | $r=2$ | 2 |
| 6 | Có ($2 \cdot 3, 3 \cdot 2$) | $r=2$ | 2 |
| 8 | Không | - | 0 |
| 9 | Có ($3 \cdot 3$) | $r=3$ | 3 |
| 12 | Không | - | 0 |
| 18 | Không | - | 0 |
| 24 | Không | - | 0 |
| 36 | Không | - | 0 |
| 72 | Không | - | 0 |

* Mảng câu trả lời $A$: $[1, 1, 1, 2, 2, 0, 3, 0, 0, 0, 0, 0]$.
* Số ước xuất hiện $S$: $6$ (có 6 giá trị $a_i \ne 0$).
* Giá trị $X$: $1 \oplus 1 \oplus 1 \oplus 2 \oplus 2 \oplus 0 \oplus 3 \oplus 0 \oplus 0 \oplus 0 \oplus 0 \oplus 0 = 1 \oplus 3 = 2$.

✅ Đã AC: 0 / 0 submissions