题面。

思路

首先 $\gcd(a,b)=g$，那 $a,b$ 肯定都得是 $g$ 的倍数。

设 $a=xg,b=yg$，$x<y$ 且 $x$ 与 $y$ 互质。我们求出 $x,y$ 的值就可以了。

题目中的 $R$ 是个新定义的函数，那就先来研究一下它的性质。

有 $R(i,j)=R(\lfloor \frac{j}{i}\rfloor,i)$。

$R(a,b)=h$，那么递归的最后一层是 $R(h,1)$。

倒数第二层应该是 $R([h,2h),h)$，再往上是 $R(h,[h^2,2h^2))$。

所以对于任意正整数 $i$，都有 $R(h,[h^i,2h^i))=h$。

结合以上两点：$R(a,b)=R(xg,yg)=R(\lfloor \frac{y}{x}\rfloor,xg)$。

我们想得到一个最小的可行解，所以考虑最小的可行 $x$ 怎么求。

$x \in [\lfloor \frac{h^i}{g}\rfloor , \lfloor \frac{2h^i}{g}\rfloor)$，想要最小解，那就让 $x= \lceil \frac{k^i}{g} \rceil$ 就好。

至于 $y$，它需要满足 $\lfloor \frac{y}{x}\rfloor=h$ 且与 $x$ 互质。满足条件的 $y$ 可以是 $x\times h+1$。

注意：$x$ 不能为 $1$。

代码

#include <cstdio>
long long T,G,H,A,B;
void solve(long long g,long long h)
{
	long long now=1;
	while(now<=g)
		now*=h;
	A=(now-1)/G+1;
	B=A*h+1;
}
int main()
{
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld%lld",&G,&H);
		solve(G,H);
		printf("%lld %lld\n",A*G,B*G);
	}
}