P5213 [SHOI2014] Super Particle Cannon.

shoi2014 day1t3

The evil giant space monster CCM (Crazy Code Monster) is about to attack the beautiful Earth. At this critical moment, the Earth Allied Forces decide to use the most advanced energy weapon on Earth—the Super Particle Cannon designed by the inventor SHTSC—to completely destroy CCM. The Super Particle Cannon consists of $n$ Super Particle launch tubes arranged vertically from top to bottom, numbered $1 \sim n$. All tubes will fire powerful Super Particle streams at the same instant. To completely destroy the evil space monster CCM, which has extremely strong regeneration ability, the Earth Allied Forces divide CCM from top to bottom into $m$ regions, numbered $1 \sim m$, and attack them separately. The $i$-th launch tube of the Super Particle Cannon will aim at region $f(i)$. The formula of $f(i)$ is: $$f(i) = (ai + b) \bmod m + 1$$ where $a$ and $b$ are given constants. However, for some unspeakable purpose, the N Consortium does not want CCM to be completely eliminated by the Super Particle Cannon. So the N Consortium remotely mind-controls the operator of the Super Particle Cannon—you—to stop the Earth forces from destroying CCM. You discover that the firing pattern of the Super Particle Cannon will cause the trajectories of different particle streams to cross. If energy reflection devices called Warp Prisms are deployed at all these intersection points, the Super Particle Cannon will overload and self-destruct. In this way, you can stop the Earth Allied Forces from using the Super Particle Cannon to destroy CCM, and become the next-generation gold medal winner of the N Consortium. To carry out this plan, you need to know how many pairs of particle streams $i, j$ satisfy $i f(j)$.

The first line contains four integers $n, m, a, b$, representing the number of launch tubes of the Super Particle Cannon, the number of regions CCM is divided into, and the constants in the formula $f$ described above.

Output one integer in a single line, the number of pairs of particle streams whose trajectories intersect.

For $10\%$ of the data, $n\leq 5 \times 10^3$. For $20\%$ of the data, $n\leq m\leq 10^6$. For an additional $20\%$ of the data, $b=0$. For $80\%$ of the data, $1\leq a\leq 1000$. For $100\%$ of the data, $n \leq m \leq 10^9$, there exists $a'$ such that $a\times a' =1 \pmod m$, and $\min \{a,a'\} \leq 1000, a,b