#CYF0057. lcm 问题

lcm 问题

题目背景

lcm(x,y)lcm(x, y) 指的是 x,yx, y 的最小公倍数,就是寻找一个能够同时被 xxyy 整除的最小正整数,比如 lcm(13,37)=481,lcm(9,6)=18lcm(13, 37) = 481, lcm(9, 6) = 18

小拓展:

最小公倍数:设 a,ba, b 为正整数,mm 为非负整数,若 ama | mbmb | m ,则称 mmaabb 的公倍数,aabb 的所有公倍数中最小的正数称为 aabb 的最小公倍数,记做 lcm(a,b)lcm(a, b) ,根据定义有 lcm(a,b)=lcm(b,a)lcm(a, b) = lcm(b, a) , 另外 lcmlcmgcdgcd 的关系为 lcm(a,b)=abgcd(a,b)lcm(a, b) = \frac{a · b}{gcd(a, b)} ,在实际代码中我们需要写 a/gcd(a,b)ba / gcd(a, b) · b​ ,防止溢出。

题目描述

现在小 C 会给你两个正整数 l,rl, r ,请你寻找出两个正整数 x,yx, y ,满足 lx<yr,llcm(x,y)rl \leq x < y \leq r, l \leq lcm(x, y) \leq r

输入格式

输入多行。

第一行输入一个正整数 tt ,代表有 tt 组测试数据。

接下来 tt 行,每行输入两个正整数 l,rl, r

输出格式

输出多行。

对于每一组测试数据,输出两个正整数,如果无法找到满足题意的答案输出两个 -1 ,否则就输出满足题意的 x,yx, y ,答案可能有多个,我们输出最小的那一组。

样例 #1

样例输入 #1

4
1 1337
13 69
2 4
88 89

样例输出 #1

1 2
13 26
2 4
-1 -1

提示

样例解释】:

  • 对于第三组样例,满足题目要求的一组 x,yx, y2 4

数据范围】:

测试点编号 l,rl, r \geq l,rl, r \leq
01 ~ 10 11 10310^3
11 ~ 15 10510^5
16 ~ 20 10910^9 101810^{18}

对于 100%100\% 的数据,保证 1t105,1l<r10181 \leq t \leq 10^5, 1 \leq l < r \leq 10^{18}