/ 
Time Limit: 10 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
正整数 n, a, b であって，a<b を満たすものが与えられます．
1\leq L\leq R を満たす整数の組 (L,R) が良い組であるとは，次の条件が成り立つことをいいます．
- L 以上 R 以下の整数のうちで a の倍数であるものの個数を n_a，b の倍数であるものの個数を n_b とするとき，n_a - n_b = n が成り立つ．
良い組は必ず存在することが証明できます．良い組のうち，R-L が最大であるものを答えてください．そのような組が複数存在する場合には，さらにそのうちで L が最小であるものを答えてください（1\leq L より L が最小のものが存在し，答えるべき (L, R) は一意に定まります）．
T 個のテストケースが与えられるので，それぞれについて答えを求めてください．
制約
- 1\leq T\leq 2\times 10^5
- 1\leq n \leq 10^6
- 1\leq a < b \leq 10^6
入力
入力は以下の形式で標準入力から与えられます．
T
\text{case}_1
\vdots
\text{case}_T
各テストケースは以下の形式で与えられます．
n a b
出力
T 行出力してください．i 行目には i 番目のテストケースについて，答えとなる組 (L,R) を次の形式で出力してください．
L R
入力例 1
1 3 3 5
出力例 1
4 35
(L,R)=(4,35) は，n_a=10, n_b=7 より良い組です．
他には例えば (1,26), (10,41) などの良い組があります．このうち (1,26) は R-L が最大ではないので答えではありません．また (10,41) は R-L は最大ですが，L が最小ではないので答えではありません．
入力例 2
5 4 3 5 6 2 4 1 1 2 123 456 789 9876 54 321
出力例 2
10 50 3 29 2 4 5473 140447 163 641411
Score : 800 points
Problem Statement
You are given positive integers n, a, and b such that a<b.
An integer pair (L,R) such that 1\leq L\leq R is said to be a good pair when the following condition holds.
- Let n_a and n_b be respectively the number of multiples of a and the number of multiples of b among the integers between L and R, inclusive. Then, n_a - n_b = n.
It can be proved that a good pair always exists. Report the good pair with the largest value of R-L. If multiple such pairs exist, report the one with the smallest L (from 1\leq L, the sought (L, R) with the smallest L exists and is unique).
You have T test cases to solve.
Constraints
- 1\leq T\leq 2\times 10^5
- 1\leq n \leq 10^6
- 1\leq a < b \leq 10^6
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\vdots
\text{case}_T
Each test case is given in the following format:
n a b
Output
Print T lines. The i-th line should contain the sought pair (L,R) for the i-th test case in the following format:
L R
Sample Input 1
1 3 3 5
Sample Output 1
4 35
(L,R)=(4,35) is a good pair since n_a=10, n_b=7.
Some other good pairs are (1,26) and (10,41). (1,26) is not the answer because it does not have the largest R-L. (10,41) is not the answer because, although it has the largest R-L, it does not have the smallest L.
Sample Input 2
5 4 3 5 6 2 4 1 1 2 123 456 789 9876 54 321
Sample Output 2
10 50 3 29 2 4 5473 140447 163 641411