P5444 [APIO2019] Strange Device

Archaeologists have discovered a strange device left behind by an ancient civilization. The device has two screens, which display two integers $x$ and $y$. After research, scientists reached the following conclusion: the device is a special clock. It starts counting the number of moments $t$ that have passed since some point in the past, but the creator displays $t$ in a strange way. If the number of moments that have passed since the device started measuring is $t$, then it displays two integers: $x = ((t + \lfloor \frac {t}{B} \rfloor) \bmod A)$, and $y = (t \bmod B)$. Here $\lfloor x \rfloor$ is the floor function, which means the greatest integer less than or equal to $x$. Archaeologists further found that the screens cannot work all the time. In fact, the screens work normally only during $n$ continuous time intervals. The $i$-th interval is from moment $l_i$ to moment $r_i$. Now scientists want to know how many different pairs $x,y$ can be displayed while the device is working. Two pairs $(x_1,y_1)$ and $(x_2,y_2)$ are different if and only if $x_1 \neq x_2$ or $y_1 \neq y_2$.

The first line contains three integers $n$, $A$, and $B$. The next $n$ lines each contain two integers $l_i$ and $r_i$, representing the $i$-th time interval during which the device can work.

Output one line containing one integer, the answer to the problem.

For the first sample, the device screens will display the following pairs. $t=4:(2,1)$ $t=7:(0,1)$ $t=8:(1,2)$ $t=9:(0,0)$ $t=17:(1,2)$ $t=18:(0,0)$ There are four different pairs in total: $(0,0),(0,1),(1,2),(2,1)$. For all data, $1 \leq n \leq 10^6,1 \leq A,B \leq 10^{18},0 \leq l_i \leq r_i \leq 10^{18}$. Let $S=\sum_{i=1}^n (r_i-l_i+1)$ and $L=\max_{i=1}^n (r_i-l_i+1)$. The detailed additional constraints and scores for subtasks are shown in the table below: | Subtask | Additional Constraints | Score | | :-----------: | :----------- | :-----------: | | 1 | $S\leq 10^6$ | 10 | | 2 | $n=1$ | 5 | | 3 | $A\times B \leq 10^6$ | 5 | | 4 | $B=1$ | 5 | | 5 | $B\leq 3$ | 5 | | 6 | $B\leq 10^6$ | 20 | | 7 | $L\leq B$ | 20 | | 8 | No additional constraints. | 30 | Translated by ChatGPT 5