Elearning CodePath – CTP Online Judge

Đẳng thức USCLN

GCDFACT

🟢 Hard #Math #Number Theory

### 📌 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` |

✅ Đã AC: 0 / 3 submissions