No.3663 LCM Decomposition
タグ : / 解いたユーザー数 29
作問者 :
sepa38
Problem Statement
You are given positive integers $N,L,R$.
Find one triple of positive integers $a,b,c$ that satisfies all of the following conditions.
- $L \leq a < b < c \leq R$
- $\operatorname{lcm}(a,b,c)=N$
Here, $\operatorname{lcm}(a,b,c)$ denotes the least common multiple of $a,b,c$.
If no triple satisfying the conditions exists, report that.
You are given $T$ test cases; solve each of them.
Constraints
- $1 \leq T \leq 1000$
- $1 \leq N \leq 10^9$
- $1 \leq L \leq R \leq 10^9$
- All input values are integers.
Input
The input is given from Standard Input in the following format.
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
Each test case is given in the following format.
$N$ $L$ $R$
Output
Print $T$ lines.
On the $i$-th line, for the $i$-th test case, print $a,b,c$ separated by spaces if a triple satisfying the conditions exists. If no such triple exists, print -1.
If there are multiple triples satisfying the conditions, any of them will be accepted.
Sample
Sample 1
Input
5 6 1 3 12 2 6 1 1 1 30 5 15 1000000000 1 1000000000
Output
1 2 3 3 4 6 -1 6 10 15 1 2 1000000000
In the $1$-st test case, taking $a = 1, b = 2, c = 3$ gives $\operatorname{lcm}(1,2,3)=6$, and all the other conditions are also satisfied.
Note that, as in the $3$-rd test case, a triple of positive integers satisfying the conditions does not always exist.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。