同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1034_最大公约数、最小公倍数

2022-5-16 18:16| 发布者: Hocassian| 查看: 75| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-2-89503497002900-Problem List-采集的数据-后羿采集器.html

Pro.ID

1034

Title

最大公约数、最小公倍数

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1034

AC

2099

Submit

4772

Ratio

43.99%

时间&空间限制

Time Limit: 1000/500 MS (Java/Others) Memory Limit: 32768/5000 K (Java/Others)

描述

求两个正整数m和n的最大公约数(greatest common divisor)和最小公倍数(least common multiple)。

普及一下知识：

1. 求GCD用"辗转相除法"的运行速度比"枚举法"快得多。

2. 最小公倍数 = m * n / 最大公约数。

输入

有多个测试用例，一个测试用例占一行，是两个正整数m和n（ 0 < m, n ≤ 100000 ），一个空格隔开。

m=-1 n=-1 表示结束。

输出

Description

求两个正整数m和n的最大公约数(greatest common divisor)和最小公倍数(least common multiple)。

普及一下知识：

1. 求GCD用"辗转相除法"的运行速度比"枚举法"快得多。

2. 最小公倍数 = m * n / 最大公约数。

Input

有多个测试用例，一个测试用例占一行，是两个正整数m和n（ 0 < m, n ≤ 100000 ），一个空格隔开。

m=-1 n=-1 表示结束。

Output

对每个测试用例输出一行，分别是m和n的最大公约数和最小公倍数，用一个空格分隔。

Sample Input

5 10
6 9
-1 -1

Sample Output

5 10
3 18

Hint

1. 枚举法，根据最大公约数、最小公倍数的定义，逐个数去试。速度较慢。

2. 用“辗转相除法”求出a,b的最大公约数c，a*b/c即最小公倍数。速度较快。

Author

John

样例输入