COCI 2020/2021 - Contest 2 - Euklid

View as PDF

Submit solution

Points: 1.50 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2020/2021 - Contest 2
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Người ta hiếm khi đề cập rằng bà của Euclid đến từ Vrsi ở Croatia. Đó là nơi ở của người anh họ - Edicul ít được biết đến hơn (nhưng không kém phần tài năng) của Euclid.

Một ngày nọ, họ đang chơi trò "phát minh ra một thuật toán". Edicul viết hai số nguyên dương trên cát. Sau đó, anh ta làm như sau: trong khi không có số nào trên cát là ~1~, anh ta đánh dấu chúng là ~(a, b)~ sao cho ~a ≥ b~. Sau đó, các con số bị xóa và anh ấy viết ~(\lfloor \frac a b \rfloor~, ~b)~ trên cát, và lặp lại quá trình. Khi một trong hai số trở thành ~1~ thì số còn lại là kết quả của thuật toán của anh ta.

Về mặt hình thức, nếu ~a~ và ~b~ là các số nguyên dương, kết quả ~R(a, b)~ của thuật toán Edicul là:

$$ R(a, b) = \begin{cases} R(b,a) & \text{nếu } a < b \\ R(\lfloor \frac a b \rfloor, b) & \text{nếu } a \geq b > 1 \\ a & \text{nếu } a \geq b = 1 \end{cases} $$

Euclid suy nghĩ một lúc và nói: "Edicul, tôi có một ý tưởng hay hơn ...", và phần còn lại là lịch sử. Thật không may, Edicul chưa bao giờ trở nên nổi tiếng vì ý tưởng của mình trong lý thuyết số. Câu chuyện buồn này đã dẫn đến câu hỏi sau:

Cho các số nguyên dương ~g~ và ~h~, hãy tìm các số nguyên dương ~a~ và ~b~ sao cho ước chung lớn nhất của chúng là ~g~ và kết quả của thuật toán Edicul ~R(a, b)~ là ~h~.

Input

Dòng đầu chứa số nguyên ~T~ (~1 \leq T \leq 40~) là số bộ test

~T~ dòng tiếp theo mỗi dòng chứa ~2~ số nguyên dương ~g_i~, ~h_i~ ~(h_i \geq 2)~

Output

Gồm ~T~ dòng. Dòng thứ ~i~ chứa ~2~ số nguyên dương ~a_i~ và ~b_i~ sao cho ~gcd~(~a_i~, ~b_i~)= ~g_i~ và ~R(a_i, b_i)~= ~h_i~

Kết quả không vượt quá ~10^{18}~ và luôn tồn tại

Nếu có nhiều đáp án, in ra đáp án bất kì

Sample Input 1

1
1 4

Sample Output 1

99 23

Sample Input 2

2
3 2
5 5

Sample Output 2

9 39
5 5

Giải thích cho ví dụ 1:

~99~ và ~23~ là hai số nguyên tố cùng nhau (có ước chung lớn nhất là 1). Ta có ~[\frac{99}{23}]~ ~= 4~ vì vậy ~R(99,23) = R(4,23) = R(23,4)~. Tiếp đến ta có ~[\frac{23}{4}] = 5~ nên ~R(23,4) = R(5,4) = R(1,4) = R(4,1) = 4~

Giải thích cho ví dụ 2:

Testcase 1, ~gcd(3,39) = 3~ và ~R(3,39) = 2~

Testcase 2, ~gcd(5,5) = 5~ và ~R(5,5) = 5~

Subtask

  • Có ~5~ test ~g = h~

  • Có ~9~ test ~h = 2~

  • Có ~9~ test ~g = h^2~

  • Có ~10~ test ~g, h \leq 20~

  • Có ~22~ test ~g, h \leq 2000~

  • Số test còn lại không có ràng buộc gì thêm.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.