💻
Elearning
CodePath
Problems
Contests
Roadmap
🐱 Scratch
🔐 Login
Ước Chung và Bội Chung
NTT01
## Đề bài Cho `q` truy vấn. Mỗi truy vấn gồm hai số nguyên dương `a` và `b`. Với mỗi truy vấn, hãy in ra: - `gcd(a, b)`: ước chung lớn nhất của `a` và `b`; - `lcm(a, b)`: bội chung nhỏ nhất của `a` và `b`. Bài này rèn kỹ thuật Euclid, một công cụ rất thường xuất hiện trong các bài số học. ## Dữ liệu vào - Dòng đầu chứa số nguyên `q`. - `q` dòng tiếp theo, mỗi dòng chứa hai số nguyên dương `a`, `b`. ## Dữ liệu ra Với mỗi truy vấn, in ra hai số `gcd(a, b)` và `lcm(a, b)` trên một dòng. ## Ràng buộc - `1 <= q <= 200000` - `1 <= a, b <= 10^9` ## Subtask - Subtask 1: `q <= 100`, `a, b <= 1000`. - Subtask 2: `q <= 10000`. - Subtask 3: ràng buộc đầy đủ. ## Ví dụ ```text 3 12 18 7 5 100 25 ``` ## Dữ liệu ra mẫu ```text 6 36 1 35 25 100 ``` ## Giải thích ví dụ - `gcd(12,18)=6`, `lcm(12,18)=36`. - `7` và `5` nguyên tố cùng nhau nên `gcd=1`, `lcm=35`.
✅ Đã AC: 2 / 2 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