1732: 【基础】多个数的最大公约数和最小公倍数 【数论基础】

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:1 Solved:1

Description

题目描述

编程求n个(n<=100)正整数Ai(Ai <= 30000, 1<=i<=n)的最大公约数和最小公倍数。假设解一定在长整数范围之内。

Input

输入

第一行为n,表示有n个正整数。

第二行有n个以空格分隔的正整数。

Output

输出

第一行是n个正整数的最大公约数。

第二行是n个正整数的最小公倍数。

Sample Input Copy

3
3 4 5

Sample Output Copy

1
60

HINT

对于最大公约数,我们可以先找出M=min{Ai},然后让j从M到1逐步递减穷举,判断所有Ai除以j的余数是否都等于0,第1个满足的j值即为解。
对于最小公倍数,设M=max{Ai},然后让j从1开始逐步递增穷举,判断M*j除以所有Ai的余数是都等于0,第1个满足的M*j值即为解。

Source/Category