Elearning CodePath – CTP Online Judge

Đẳng thức USCLN

GCDFACT

🟢 Easy #Math

### 📌 Thông tin chung

---

### 📝 Bài toán

Cho $N$ số nguyên dương $A_1, A_2, \dots, A_N$ và $M$ số nguyên dương $B_1, B_2, \dots, B_M$.

Nhiệm vụ là kiểm tra tính đúng sai của đẳng thức sau:
$GCD(A_1!, A_2!, \dots, A_N!) = B_1! \cdot B_2! \cdot \dots \cdot B_M!$

Trong đó, $GCD(x_1, x_2, \dots, x_k)$ là ước chung lớn nhất của các số $x_1, x_2, \dots, x_k$.

---

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

Dữ liệu vào từ file `gcdfact.inp` gồm:

* **Dòng 1:** Ghi số nguyên $T$ – số lượng bộ dữ liệu kiểm thử.
* **$T$ khối dữ liệu tiếp theo, mỗi khối gồm 3 dòng:**
    * Dòng 1: Số nguyên $N$.
    * Dòng 2: $N$ số nguyên dương $A_1, A_2, \dots, A_N$ (biểu thức vế trái).
    * Dòng 3: Số nguyên $M$ (số lượng thừa số ở vế phải).
    * Dòng 4: $M$ số nguyên dương $B_1, B_2, \dots, B_M$ (biểu thức vế phải).

**Giới hạn (Ràng buộc):**
$* 1 \le T \le 10 $
$* 1 \le N, M \le 10^5 $
$* 1 \le A_i, B_i \le 10^6$

---

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

Ghi ra file `gcdfact.out`. Với mỗi bộ dữ liệu kiểm thử, in ra trên một dòng duy nhất chuỗi:
* **YES** nếu đẳng thức là đúng.
* **NO** nếu đẳng thức là sai.

---

### 🧪 Phân Subtask & Ràng buộc

| \# | Điểm | Ràng buộc bổ sung | 
| :--- | :--- | :--- | :--- |
| **1** | 20% | $N, M \le 5$ và $A_i, B_i \le 10$ | 
| **2** | 30% | $N, M \le 100$ và $A_i, B_i \le 100$ | 
| **3** | 10% | Tất cả $A_i, B_i$ là số nguyên tố | 
| **4** | 40% | $N, M \le 10^5$ và $A_i, B_i \le 10^6$ |

---

### Ví dụ

| Input (`gcdfact.inp`) | Output (`gcdfact.out`) |
| :--- | :--- |
| `2` `5` `1 2 3 4 5` `3` `6 30 15` `3` `6 30 15` `3` `1 2 3` | `YES` `NO` |

**Giải thích Ví dụ 1:**
* $A = [1, 2, 3, 4, 5] \implies A_{\min} = 1$. Vế trái: $1! = 1$.
* $B = [6, 30, 15]$. Vế phải: $6! \cdot 30! \cdot 15!$.
* Đẳng thức: $1! = 6! \cdot 30! \cdot 15!$. Điều này SAI (1 $\ne$ số rất lớn).
> **Lưu ý:** Dựa vào Output mẫu là **YES**, có khả năng đề bài gốc là $\text{GCD}(A_1, \dots, A_N)! = \text{GCD}(B_1, \dots, B_M)!$. Nếu tuân theo đề bài đã cho $A_{\min}! = B_1! \cdot B_2! \cdot \dots \cdot B_M!$, thì test 1 phải là **NO**. Ta sẽ tuân theo **đẳng thức đã viết** và giả định test mẫu có vấn đề hoặc công thức gốc khác.

**Tuân theo công thức đã chuẩn hóa:** $\text{GCD}(A_1!, \dots, A_N!) = A_{\min}!$.

* **Test 1:** $A_{\min}=1$. Vế trái: $1!$. Vế phải: $6! \cdot 30! \cdot 15!$. $1! \ne \text{Vế phải}$. $\implies$ **NO**.
* **Test 2:** $A_{\min}=3$. Vế trái: $3! = 6$. Vế phải: $1! \cdot 2! \cdot 3! = 1 \cdot 2 \cdot 6 = 12$. $6 \ne 12$. $\implies$ **NO**.

---

### 💡 Gợi ý Lý thuyết số

1.  **Tính chất GCD của Giai thừa:** Ước chung lớn nhất của nhiều số giai thừa luôn bằng giai thừa của số nhỏ nhất trong chúng:
    $GCD(A_1!, A_2!, \dots, A_N!) = (\min(A_1, A_2, \dots, A_N))!$
    Gọi $A_{\min} = \min(A_1, A_2, \dots, A_N)$. Khi đó, đẳng thức trở thành:
    $    A_{\min}! = B_1! \cdot B_2! \cdot \dots \cdot B_M!$

2.  **Phân tích Nguyên tố:** Để kiểm tra đẳng thức giai thừa này, ta sử dụng định lý Legendre (hoặc công thức cơ bản) để kiểm tra số mũ của mỗi số nguyên tố $p$ trong cả hai vế.
    * Số mũ của $p$ trong $A_{\min}!$ là $E_p(A_{\min}!) = \sum_{k=1}^{\infty} \left\lfloor \frac{A_{\min}}{p^k} \right\rfloor$.
    * Số mũ của $p$ trong $B_1! \cdot \dots \cdot B_M!$ là $\sum_{j=1}^{M} E_p(B_j!)$.
    * Đẳng thức đúng $\iff$ Số mũ của **mọi** số nguyên tố $p \le A_{\min}$ là bằng nhau ở cả hai vế.

3.  **Thuật toán:**
    * Tìm $A_{\min}$.
    * Sàng Eratosthenes để tìm tất cả các số nguyên tố $p \le A_{\min}$.
    * Với mỗi $p$, tính $E_p(A_{\min}!)$ và $\sum E_p(B_j!)$. Nếu chúng không bằng nhau $\rightarrow$ NO.
    * Nếu tất cả các số nguyên tố đều thỏa mãn $\rightarrow$ YES.

✅ Đã AC: 1 / 2 submissions