P5887 Ringed Genesis

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

有一个长长的环，环由 $n$ 个格子首尾相接形成，依次编号 $0$ 至 $n-1$。 还有一种动物——兔子。兔子的步长为 $k$。若兔子当前在第 $i$ 个格子，那么下一秒它将跳到第 $(i+k)\bmod n$ 个格子。 现在有 $m$ 只兔子，第 $i$ 只兔子的初始格子为第 $p_i$ 个格子。随着时间的流逝，有些格子被兔子经过了，有些却一直没有被兔子经过。 你需要求出的是，有多少个格子永远不可能被兔子经过。

无

无

子任务 1（$10\%$）：$k=1$。 子任务 2（$20\%$）：$k|n$，也即 $\gcd(k,n)=k$。 子任务 3（$25\%$）：$1\leq n\leq 1000$，$1\leq m\leq 1000$。 子任务 4（$45\%$）：无特殊限制。 对于全部数据，$1 \leq n \leq 10^6$，$1 \leq m \leq 10^6$，$1 \leq k \leq n$。