C - Gear Synchronization Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は、N 個の歯車が一列に並んだ装置を組み立てました。歯車には 1 から N まで順に番号が付けられており、隣り合う歯車 i と歯車 i+1（1 \leq i \leq N-1）は互いにかみ合っています。

各歯車 i（1 \leq i \leq N）には T_i 枚の歯があります。歯車 i と歯車 i+1 がかみ合っているとき、一方が回転すると他方も連動して回転します。かみ合う2つの歯車は同じ数だけ歯が進むため、歯車 i が1回転（T_i 歯分）する間に歯車 i+1 は \frac{T_i}{T_{i+1}} 回転します。すなわち、歯車 i の回転数と歯車 i+1 の回転数の比は T_{i+1} : T_i です（歯数が多い歯車ほどゆっくり回転します）。

各歯車にはちょうど 1 枚だけ印の付いた歯があります。歯車がちょうど正の整数回だけ回転すると、すべての歯は元の位置に戻るため、印の付いた歯も元の位置に戻ります。逆に、回転数が正の整数でなければ印は元の位置に戻りません。なお、隣り合う歯車は互いに逆方向に回転しますが、印が元の位置に戻るかどうかは回転の向きには依存せず、回転数のみで決まります。

歯車 1 を回すと、かみ合いにより歯車 2, 3, \ldots, N も連動して回転します。歯車 1 の回転数を R（R > 0）としたとき、すべての歯車の印が同時にそれぞれの元の位置に戻るような最小の正の R を求めてください。ここで回転数とは、回転した回数を表す正の実数であり、回転の向きによらない量です。

R は必ず正の有理数になることが証明できます。R を既約分数 \frac{P}{Q}（P, Q は正の整数、\gcd(P, Q) = 1）で表し、P と Q を / で区切って出力してください。R が整数の場合は P/1 の形式で出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq T_i \leq 10^9
  • 入力はすべて整数である。
  • 答えを既約分数 \frac{P}{Q} で表したとき、P, Q はともに 10^{18} 以下であることが保証される。

入力

N
T_1 T_2 \ldots T_N
  • 1 行目には、歯車の個数を表す整数 N が与えられる。
  • 2 行目には、各歯車の歯の枚数を表す N 個の整数 T_1, T_2, \ldots, T_N がスペース区切りで与えられる。

出力

すべての歯車の印が同時にそれぞれの元の位置に戻るような歯車 1 の最小の正の回転数を既約分数で表したとき、分子 P と分母 Q を / で区切って 1 行で出力せよ。ただし、答えが整数の場合は P/1 の形式で出力せよ。

入力例 1

3
8 12 6

出力例 1

3/1

入力例 2

2
6 10

出力例 2

5/1

入力例 3

10
18 24 30 45 60 72 90 120 150 180

出力例 3

100/1

入力例 4

30
840 1260 1680 2100 2520 3150 3360 4200 5040 6300 6720 7560 8400 10080 12600 15120 16800 20160 25200 27720 30240 33600 37800 42000 50400 55440 60480 75600 83160 100800

出力例 4

19800/1

入力例 5

1
1000000000

出力例 5

1/1

Score : 366 pts

Problem Statement

Takahashi has assembled a device consisting of N gears arranged in a row. The gears are numbered from 1 to N in order, and adjacent gears i and i+1 (1 \leq i \leq N-1) mesh with each other.

Each gear i (1 \leq i \leq N) has T_i teeth. When gear i and gear i+1 are meshed, if one rotates, the other rotates accordingly. Since two meshing gears advance the same number of teeth, while gear i makes one full rotation (T_i teeth), gear i+1 rotates \frac{T_i}{T_{i+1}} times. In other words, the ratio of the number of rotations of gear i to gear i+1 is T_{i+1} : T_i (a gear with more teeth rotates more slowly).

Each gear has exactly one marked tooth. When a gear rotates exactly a positive integer number of times, all teeth return to their original positions, so the marked tooth also returns to its original position. Conversely, if the number of rotations is not a positive integer, the mark does not return to its original position. Note that adjacent gears rotate in opposite directions, but whether the mark returns to its original position depends only on the number of rotations, not on the direction of rotation.

When gear 1 is rotated, gears 2, 3, \ldots, N also rotate accordingly through the meshing. Let R (R > 0) be the number of rotations of gear 1. Find the smallest positive R such that the marks on all gears simultaneously return to their respective original positions. Here, the number of rotations is a positive real number representing how many times the gear has rotated, regardless of the direction of rotation.

It can be proven that R is always a positive rational number. Express R as an irreducible fraction \frac{P}{Q} (P, Q are positive integers, \gcd(P, Q) = 1), and output P and Q separated by /. If R is an integer, output it in the format P/1.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq T_i \leq 10^9
  • All inputs are integers.
  • It is guaranteed that when the answer is expressed as an irreducible fraction \frac{P}{Q}, both P and Q are at most 10^{18}.

Input

N
T_1 T_2 \ldots T_N
  • The first line contains an integer N representing the number of gears.
  • The second line contains N integers T_1, T_2, \ldots, T_N separated by spaces, representing the number of teeth on each gear.

Output

Output the numerator P and denominator Q of the irreducible fraction representing the smallest positive number of rotations of gear 1 such that the marks on all gears simultaneously return to their respective original positions, separated by / on a single line. If the answer is an integer, output it in the format P/1.

Sample Input 1

3
8 12 6

Sample Output 1

3/1

Sample Input 2

2
6 10

Sample Output 2

5/1

Sample Input 3

10
18 24 30 45 60 72 90 120 150 180

Sample Output 3

100/1

Sample Input 4

30
840 1260 1680 2100 2520 3150 3360 4200 5040 6300 6720 7560 8400 10080 12600 15120 16800 20160 25200 27720 30240 33600 37800 42000 50400 55440 60480 75600 83160 100800

Sample Output 4

19800/1

Sample Input 5

1
1000000000

Sample Output 5

1/1