[VTT Q4 Contest 11] Bài 1: Bội chung nhỏ nhất [LCM]

Xem dạng PDF

Gửi bài giải


Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: LCM.INP
Output: LCM.OUT

Dạng bài
Ngôn ngữ cho phép
C++, Pascal, PyPy, Python

Với hai số nguyên dương ~x, y~, ký hiệu ~LCM(x, y)~ là số nguyên dương nhỏ nhất đồng thời là bội của cả ~x~ và ~y~. Chẳng hạn ~LCM(3, 4) = 12~, ~LCM(6, 9) = 18~.

Cho hai số nguyên dương ~l~ và ~r~. Hãy tìm hai số nguyên dương ~x, y~ sao cho ~l \le x < y \le r~ và bội chung nhỏ nhất của chúng cũng nằm trong đoạn ~[l, r]~, tức ~l \le LCM(x, y) \le r~.

Dữ liệu

  • Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 10^5~) là số truy vấn.
  • ~t~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~l~ và ~r~ (~1 \le l < r \le 10^9~) mô tả truy vấn thứ ~i~.

Kết quả

  • In ra ~t~ dòng, dòng thứ ~i~ gồm hai số nguyên ~x, y~ là một đáp án của truy vấn thứ ~i~. Nếu có nhiều cặp ~(x, y)~ thỏa mãn thì in một cặp bất kỳ. Nếu không tồn tại cặp nào thì in ra hai số ~-1~.

Ví dụ

LCM.INP

2
1 20
14 15

LCM.OUT

3 5
-1 -1

Giải thích: Với truy vấn thứ nhất, cặp ~(3, 5)~ có ~LCM = 15~ nằm trong ~[1, 20]~. Với truy vấn thứ hai, chỉ có cặp ~(14, 15)~ mà ~LCM = 210~ vượt quá ~15~, nên không có đáp án.

Giới hạn

  • Subtask 1 (30% số điểm): ~r \le 100~.
  • Subtask 2 (30% số điểm): ~t = 1~, ~r \le 10^7~.
  • Subtask 3 (40% số điểm): không có ràng buộc gì thêm.

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.