P5887 Ringed Genesis

Enzyme runs through the Ringed Genesis, just like Rabbit runs through a Ring.

There is a long ring made by connecting $n$ cells end to end, numbered from $0$ to $n-1$ in order. There is also an animal called a rabbit. The rabbit’s step length is $k$. If the rabbit is currently on the $i$-th cell, then in the next second it will jump to the $((i+k)\bmod n)$-th cell. Now there are $m$ rabbits. The initial cell of the $i$-th rabbit is the $p_i$-th cell. As time goes by, some cells are visited by rabbits, while some cells are never visited. You need to find how many cells can never be visited by any rabbit.

Read input from standard input. The first line contains three positive integers $n, m, k$, representing the ring length, the number of rabbits, and the step length. The second line contains $m$ non-negative integers $p_1, p_2, \dots, p_m$, representing the initial cells of the rabbits.

Write output to standard output. Output one line with one integer, which is the answer.

Subtask 1 ($10\%$): $k = 1$. Subtask 2 ($20\%$): $k \mid n$, i.e. $\gcd(k, n) = k$. Subtask 3 ($25\%$): $1 \leq n \leq 1000$, $1 \leq m \leq 1000$. Subtask 4 ($45\%$): no special constraints. For all testdata, $1 \leq n \leq 10^6$, $1 \leq m \leq 10^6$, $1 \leq k \leq n$. Translated by ChatGPT 5