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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <iostream> #define SIZE 1000001 using namespace std; long long n, k, a, cnt[SIZE], i, j, x = 0; int main() { cin >> n >> k; for (i = 0; i < n; ++i) { cin >> a; ++cnt[a]; } for (i = k + 1; i < SIZE; ++i) { if (cnt[i] > 0) { for (j = k; j < SIZE; j += i) //add each time k + 1 if (cnt[j] > 0) { if (i == j) { x += cnt[i] * (cnt[i] - 1); } else { x += cnt[j] * cnt[i]; } } } } cout << x << endl; } |
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).
У Вас все переменные, включая счетчики цикла, — глобальные. В Паскале по-другому не выходило, но в С++ так не принято. Когда у Вас в коде будет 50 функций, вызывающих друг друга, и в каждой — циклы, глобальные переменные станут крайне неудобными.
Какой алгоритм Вы применили и какова его сложность? В главе «решение» Вы просто попытались пересказать код, но не пояснить, почему написан такой код, а не другой.
Ещё и отступы…