#P2406. 最小和

最小和

题目背景

RSA算法基于一个十分简单的数论事实:将两个大素数相乘十分容易,但是想要对其乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥。所以今天只有短的RSA钥匙才可能被强力方式解破。

题目描述

已知 aabb 是正整数且 aba \leq b

求满足条件且 x+yx+y 的值最小的 xxyy

条件:

  • gcd(x,y)=a\gcd(x,y) = a
  • lcm(x,y)=b\mathrm{lcm}(x,y) = b
  • xyx \leq y

输入格式

多组数据,EOF 判断结束

共有不超过 10310^3 行,每行两个数 aabb

输出格式

输出和输入文件一样多的行,每行一个半角空格隔开的两个数 xxyy

3 60
12 15
200 20000
300 30000
400 40000
800 5000
1200 7500
1600 10000

提示

3a,b<2633 \leq a, b < 2^{63}

EOF 结束,没有代表行数的 nn,第一行就是数据。

数据随机生成。