问题 D: 【基础】公约数公倍数

问题 D: 【基础】公约数公倍数

题目描述

  小T是个多才多艺的同学,不仅擅长国画,还是个数学爱好者,他小学六年级就代表龙城书院参加了“华罗庚金杯”少年数学邀请赛。最近小T对最大公约数和最小公倍数产生了浓厚的兴趣,并学会了用辗转相除法求两个自然数的最大公约数,但小T并不满足于会用辗转相除法,他是一个酷爱钻研的人,无论学什么都喜欢刨根问底,他想能不能把这个问题反过来,即已知两个自然数A和B的最大公约数G和最小公倍数L,问有多少对满足条件的自然数对A和B?

输入

仅有一行包含两个用空格隔开的自然数G和L,数据保证L一定是G的倍数并且满足1≤G≤L≤1,000,000,000。

输出

包含若干行,每行输出一对自然数A和B(A≤B),它们满足GCD(A,B)=G,LCM(A,B)=L。这里GCD(A,B)表示A和B的最大公约数,LCM(A,B) 表示A和B的最小公倍数。输出时要求按照A(每行第一个数)从小到大输出,两数之间严格用一个空格隔开,行末不能有空格。

样例输入输出

输入#1 复制
4 48
输出#1 复制
4 48
12 16

提示

【样例解释】 两个数的最大公约数要等于4、最小公倍数要等于48,这两个数只可能是4和48或者12和16,因为4比12小,所以第一行输出4和48,第二行输出12和16。有关辗转相除法的知识请参阅试机文件夹中的word文档“说明.doc”。
【友情提醒】 对于任意两个自然数A和B都有,A*B=GCD(A,B)*LCM(A,B),即两个自然数之积等于它们的最大公约数与最小公倍数之积,这一点对你思考问题和检验结果都会有所帮助。
【数据范围】
30%的数据满足:1≤G≤L≤500
50%的数据满足:1≤G≤L≤10,000
100%的数据满足:1≤G≤L≤1,000,000,000

序号 标题 作者 发表时间 费用 订购数 操作