5506: 整除问题
[Creator : ]
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$ 获得的分数,请问最后你计算将获得的总分数。
计算每个 $a_i$ 获得的分数,请问最后你计算将获得的总分数。
Input
第一行 $n$,表示共有 $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$。
对于 $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$。
第二个数据 $6$ 获得的分数为 $0$。因为没有其他数据是其倍数。
第三个数据 $2$ 的倍数有 $6$ 和 $8$,因为 $8$ 是第四个数据,所以获得的分数为 $4$。
第四个数据 $8$ 获得的分数为 $0$。
因此总和是 $2+0+4+0=6$。