e-olymp 8678. Birches

Task

The State National Park $Q$ recently acquired a beautiful birch avenue consisting of $n$ trees. Each tree has a height of $H_i$.

International Classification of national parks is a list of the most beautiful nature reserves in the world. Used to rank parks such a thing as $distinctiveness$ which is understood as the number of pairs ($i$, $j$), for which the observed ratio of $H_i$ $mod$ $H_j$ = $k$, where $k$ is a special number, which is selected by the Expert Council of the international organization of national parks.

What $distinctiveness$ has national park state $Q$?

Input

The first line has two positive integers $n$ and $k$ [latex]\left(1\leqslant n\leqslant 10^5, 0\leqslant k\leqslant 10^6\right)[/latex] — the number of trees in the national park and a special number of the advisory council, respectively.

The second line has $n$ numbers $H_i$ [latex]\left(1\leqslant H_i\leqslant 10^6\right)[/latex] — the height of the trees in the park.

Output

In the single line print $Q$ national park $distinctiveness$.

Tests

Input Output

1

5 1

1 2 3 4 5

8

2

6 2

2 6 7 8 10 14

8

3

15 6

1 4 5 6 9 13 15 16 19 20 2124 27 45 49

14

4

7 3

1 5 7 8 9 23 46

2

5

10 15

23 26 67 79 82 110 118 200 450 900

2

Program code

Solution

To solve this problem, we will count the number of identical elements, while entering the array. Next, if $i$ and $j$ were met more than $0$ times and $i$ is not equal $j$, we add the counter x + = cnt [j] * cnt [i], and if $i$ = $j$ — x + = cnt [i] * (cnt [i] - 1).

Links

2 thoughts on “e-olymp 8678. Birches

  1. У Вас все переменные, включая счетчики цикла, — глобальные. В Паскале по-другому не выходило, но в С++ так не принято. Когда у Вас в коде будет 50 функций, вызывающих друг друга, и в каждой — циклы, глобальные переменные станут крайне неудобными.

    Какой алгоритм Вы применили и какова его сложность? В главе «решение» Вы просто попытались пересказать код, но не пояснить, почему написан такой код, а не другой.

Добавить комментарий