GCD pairs counting - MarisaOJ: Marisa Online Judge

Given a sequence of integers

$A$ consisting of n elements. For each integer

$i$ from

$1$ to

$n$ , count how many pairs of integers in sequence A have the greatest common divisor (GCD) equal to

$i$ . ### Input - The first line contains an integer

$n$ . - The second line contains n integers

$A_i$ . ### Output - Output

$n$ integers, where the

$i^{th}$ integer is the number of pairs of integers with the smallest GCD equal to

$i$ . ### Constraints -

$1 \le n \le 10^6$ . -

$1 \le A_i \le n$ ### Example Input:

$8 5 1 5 6 8 8 3 5$

Output:

$21 2 1 0 3 0 0 1$

Topic

Math

Rating

1500

Solution (0)

Solution