Flatten

题目描述

给定 $N$ 个正整数 $A_1,...,A_N$。 考虑满足以下条件的正整数 $B_1, ..., B_N$。 条件：对于任意 $i, j$ 满足 1 \leq i < j \leq N，都有 $A_i B_i = A_j B_j$。 求满足该条件的 $B_1,...,B_N$ 的 $B_1 + ... + B_N$ 的最小可能值。 由于答案可能非常大，请将和对 ($10^9 +7$) 取模后输出。

输入格式

输入以标准输入给出，格式如下： $N$ $A_1$ $...$ $A_N$

输出格式

输出满足条件的 $B_1,...,B_N$ 的 $B_1 + ... + B_N$ 的最小可能值，对 ($10^9 +7$) 取模后。

3
2 3 4

13

5
12 12 12 12 12

5

3
1000000 999999 999998

996989508

提示

$1 \leq N \leq 10^4$ $1 \leq A_i \leq 10^6$ 输入中的所有数值都是整数。可以令 $B_1=6$，$B_2=4$，和 $B_3=3$，此时条件被满足。
我们可以令所有 $B_i$ 都为 $1$。
将和对 $(10^9+7)$ 取模后输出。

标签: AtCoder|abc152E

来源

AtCoder|abc152E