AT_abc152_e [ABC152E] Flatten

题目描述

给定 $N$ 个正整数 $A_1,\ldots,A_N$。

请考虑满足以下条件的正整数 $B_1,\ldots,B_N$。

条件：对于任意满足 $1 \leq i < j \leq N$ 的 $i,j$，都有 $A_i B_i = A_j B_j$。

请你求出所有满足条件的 $B_1,\ldots,B_N$ 中 $B_1 + \cdots + B_N$ 的最小值。

但由于答案可能非常大，请输出其对 $10^9+7$ 取模的结果。

输入格式

输入以如下格式从标准输入读入。

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

请输出满足条件的 $B_1,\ldots,B_N$ 中 $B_1 + \cdots + B_N$ 的最小值对 $10^9+7$ 取模的结果。

输入输出样例 #1

输入 #1

3
2 3 4

输出 #1

13

输入输出样例 #2

输入 #2

5
12 12 12 12 12

输出 #2

5

输入输出样例 #3

输入 #3

3
1000000 999999 999998

输出 #3

996989508

说明/提示

限制条件

• $1 \leq N \leq 10^4$
• $1 \leq A_i \leq 10^6$
• 输入中的所有值均为整数。

样例解释 1

取 $B_1=6$，$B_2=4$，$B_3=3$ 时可以满足条件。

样例解释 2

将所有 $B_i$ 都取为 $1$ 即可。

样例解释 3

请输出和对 $10^9+7$ 取模的结果。

由 ChatGPT 4.1 翻译