607 . Rhythm Doctor
TopCoder
Tags
Description
每個人的生命中都有各自的拍數。
假設大家的拍子都從第 $1$ 秒開始，請問下一次大家剛好在同個時間打拍子是什麼時候？
- 保證答案在
long long範圍內。
舉例來說，如果有兩個人，分別為 A 和 B，A 和 B 的拍數分別為 $3$ 和 $4$，那麼下次同時打拍子，如下圖，會在第 $12$ 秒。因此答案為 $12$。
官方的小提示
- 提供一個很快的最大公因數函式，可以使用著個函式求解。
long long GCD (long long a, long long b) {
if(a == 0 || b == 0)
return a + b;
return GCD(b, a % b);
}
Input Format
一開始輸入一行，其只有一個 $n$，表示接下來有幾個人的心跳拍子數。
接下來輸入 $n$ 行，每行有一個數字 $p_i$，表示第 $i$ 個人的心跳拍子數。
- $1 \le n \le 10^ 5$
- $1 \le p_i \le 2^ {63}-1$
Output Format
輸出一行一個整數，表示下一次大家剛好在同個時間打拍子在什麼時候。
- 保證答案可以用
long long保存，也就是答案會介於 $-2^ {63}$ 和 $2^ {63}-1$ 之間。
Sample Input 1
2
4 3
4 3
Sample Output 1
12
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~5 | 答案可用 int 保存 | 30 |
| 3 | 0~10 | 無額外限制 | 70 |