题目背景
lcm(x,y) 指的是 x,y 的最小公倍数,就是寻找一个能够同时被 x 和 y 整除的最小正整数,比如 lcm(13,37)=481,lcm(9,6)=18 。
小拓展:
最小公倍数:设 a,b 为正整数,m 为非负整数,若 a∣m 且 b∣m ,则称 m 为 a 和 b 的公倍数,a 和 b 的所有公倍数中最小的正数称为 a 和 b 的最小公倍数,记做 lcm(a,b) ,根据定义有 lcm(a,b)=lcm(b,a) , 另外 lcm 和 gcd 的关系为 lcm(a,b)=gcd(a,b)a⋅b ,在实际代码中我们需要写 a/gcd(a,b)⋅b ,防止溢出。
题目描述
现在小 C
会给你两个正整数 l,r ,请你寻找出两个正整数 x,y ,满足 l≤x<y≤r,l≤lcm(x,y)≤r 。
输入格式
输入多行。
第一行输入一个正整数 t ,代表有 t 组测试数据。
接下来 t 行,每行输入两个正整数 l,r 。
输出格式
输出多行。
对于每一组测试数据,输出两个正整数,如果无法找到满足题意的答案输出两个 -1
,否则就输出满足题意的 x,y ,答案可能有多个,我们输出最小的那一组。
样例 #1
样例输入 #1
4
1 1337
13 69
2 4
88 89
样例输出 #1
1 2
13 26
2 4
-1 -1
提示
样例解释】:
- 对于第三组样例,满足题目要求的一组 x,y 为
2 4
。
数据范围】:
测试点编号 |
l,r≥ |
l,r≤ |
01 ~ 10 |
1 |
103 |
11 ~ 15 |
105 |
16 ~ 20 |
109 |
1018 |
对于 100% 的数据,保证 1≤t≤105,1≤l<r≤1018 。