题目描述
考古学家发现古代文明留下了一种奇怪的装置。该装置包含两个屏幕,分别显示两个整数 x 和 y。
经过研究,科学家对该装置得出了一个结论:该装置是一个特殊的时钟,它从过去的某个时间点开始测量经过的时刻数 t,但该装置的创造者却将 t 用奇怪的方式显示出来。若从该装置开始测量到现在所经过的时刻数为 t,装置会显示两个整数:x=((t+⌊Bt⌋)modA),与 y=(tmodB)。这里 ⌊x⌋ 是下取整函数,表示小于或等于 x 的最大整数。
考古学家通过进一步研究还发现,该装置的屏幕无法一直工作。实际上,该装置的屏幕只在 n 个连续的时间区间段中能正常工作。第 i 个时间段从时刻 li 到时刻 ri。现在科学家想要知道有多少个不同的数对 (x,y) 能够在该装置工作时被显示出来。
两个数对 (x1,y1) 和 (x2,y2) 不同当且仅当 x1=x2 或 y1=y2。
输入格式
第一行包含三个整数 n,A 与 B。
接下来 n 行每行两个整数 li,ri,表示装置可以工作的第 i 个时间区间。
输出格式
输出一行一个整数表示问题的答案。
样例 1
3 3 3
4 4
7 9
17 18
4
对于第一个样例,装置屏幕将显示如下这些数对。
t |
(x,y) |
4 |
(2,1) |
7 |
(0,1) |
8 |
(1,2) |
9 |
(0,0) |
17 |
(1,2) |
18 |
(0,0) |
共有四个不同的数对:(0,0),(0,1),(1,2),(2,1)。
3 5 10
1 20
50 68
89 98
31
2 16 13
2 5
18 18
5
数据范围与提示
对于全部数据,1≤n≤106,1≤A,B≤1018,0≤li≤ri≤1018,ri<li+1。
令 S=i=1∑n(ri−li+1) 与 L=i=1maxn(ri−li+1)。
详细子任务附加限制与分值如下表。
子任务 |
附加限制 |
分值 |
1 |
S≤106 |
10 |
2 |
n=1 |
5 |
3 |
A⋅B≤106 |
4 |
B=1 |
5 |
B≤3 |
6 |
B≤106 |
20 |
7 |
L≤B |
8 |
无附加限制 |
30 |