💻
Elearning
CodePath
Problems
Contests
Roadmap
🔐 Login
CMATUS X MINHTPC HỌC EUCLID
G62489
Không lâu trước đây, Camtus đã học được thuật toán Euclid để tìm **ước chung lớn nhất (GCD)** của hai số. Ước chung lớn nhất của hai số $a$ và $b$ là số lớn nhất chia hết cho cả $a$ và $b$. Với kiến thức này, Camtus có thể giải được một bài toán mà trước đây cô ấy chưa làm được. MINHTPC có một bảng gồm $n$ hàng và $m$ cột, trong đó số nguyên $a_{i,j}$ nằm tại giao điểm của hàng thứ $i$ và cột thứ $j$. Camtus muốn đi từ **ô trên cùng bên trái** (giao điểm hàng 1, cột 1) đến **ô dưới cùng bên phải** (giao điểm hàng $n$, cột $m$), đồng thời tìm **ước chung lớn nhất của tất cả các số nằm trên đường đi**. Camtus **chỉ được phép di chuyển xuống dưới hoặc sang phải**. Cô ấy đã thử nhiều đường đi khác nhau và thu được các giá trị GCD khác nhau. Camtus muốn biết **giá trị GCD lớn nhất có thể đạt được**. Do mệt mỏi với việc tự tính toán do bói bài Tarot tình yêu quá nhiều , Camtus nhờ bạn giúp tìm **GCD lớn nhất của các số trên một đường đi hợp lệ từ ô trên cùng bên trái đến ô dưới cùng bên phải**. --- ### Input - Dòng đầu tiên chứa số nguyên $t$ — số lượng test. - Với mỗi test: - Dòng đầu tiên chứa hai số nguyên $n, m$ — số hàng và số cột của bảng. - $n$ dòng tiếp theo, dòng thứ $i$ chứa $m$ số nguyên $a_{i,j}$ — giá trị tại ô hàng $i$, cột $j$. --- ### Output - Với mỗi test, in ra **một số nguyên** là **giá trị GCD lớn nhất có thể** trên một đường đi hợp lệ từ ô $(1,1)$ đến ô $(n,m)$. --- ### Ràng buộc - $1 \le t \le 10^4$ - $1 \le n, m \le 100$ - $1 \le a_{i,j} \le 10^6$ - Tổng $n \cdot m$ của tất cả các test **không vượt quá** $2 \cdot 10^5$ --- ### Ví dụ **Input** 3 2 3 30 20 30 15 25 40 3 3 12 4 9 3 12 2 8 3 12 2 4 2 4 6 8 1 3 6 9 **Output** 10 3 1
✅ Đã AC: 2 / 4 submissions
⬅ Contest
🚀 Nộp bài
💡 Gợi ý AI
📌 Bài kế
📋 Copy đề
⚙️
⬅ Contest
🚀 Nộp bài
💡 Gợi ý
📌 Bài kế
📋 Copy
📖 Hướng dẫn học tập
Học trò tri ân
☕ Một ly cà phê sẻ chia
Bạn bè ủng hộ
🍜 Một bát phở ấm lòng
💳 Quét mã ủng hộ tuỳ tâm nhé!
💬 Liên hệ Zalo!
Đóng