Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1年前

09/10
20:07
暴力

[bzoj 4146] [AMPPZ2014]Divisors

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 给定一个序列a[1],a[2],...,a[n]。求满足i!=j且a[i]|a[j]的二元组(i,j)的个数。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行包含一个正整数n(1<=n<=2000000),表示序列长度。
第二行包含n个正整数,依次表示a[1],a[2],...,a[n](1<=a[i]<=2000000)。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

一个整数,即满足条件的二元组的个数。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

5
2 4 5 2 6

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

6

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

满足条件的6组分别为(1,2),(1,4),(1,5),(4,1),(4,2),(4,5)。

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

暴力,对于范围内每个x|y都累计进答案即可

c++:

pascal:

 

[bzoj 4146] [AMPPZ2014]Divisors