Problem5506--整除问题

5506: 整除问题

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

给定 $n$ 个正整数 $\{a_1,\ a_2,\ \cdots,\ a_i,\ \cdots,\ a_n\}$,对于一个 $a_i$,如果存在一个 $a_j\ (1 \leq j \leq n, i \neq j)$ 使得 $a_j$ 除以 $a_i$ 的余数为$0$,那么你将获得分数 $j$,当有存在多个 $a_j$ 时,我们取获得分数最多的 $a_j$。
计算每个 $a_i$ 获得的分数,请问最后你计算将获得的总分数。

Input

第一行 $n$,表示共有 $n$ 个数。
第二行共 $n$个用空格隔开的整数。

Output

仅一个整数,表示能获得的最多的分数

Constraints

对于 $40\%$ 的数据,$n \leq 1,000$;
对于 $80\%$ 的数据,$n \leq 100,000$,其中 $20\%$ 数据 $a_i \leq 50$;
对于 $100\%$ 的数据,$n \leq 5,000,000,\ a_i \leq 200,000$。

Sample 1 Input

4
3 6 2 8

Sample 1 Output

6
第一个数据 $3$ 获得的分数为 $2$。因为第二个数据 $6$ 可以整除。
第二个数据 $6$ 获得的分数为 $0$。因为没有其他数据是其倍数。
第三个数据 $2$ 的倍数有 $6$ 和 $8$,因为 $8$ 是第四个数据,所以获得的分数为 $4$。
第四个数据 $8$ 获得的分数为 $0$。
因此总和是 $2+0+4+0=6$。

Source/Category