#2084. 「APIO2019」奇怪装置

内存限制:512 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: StudyingFather

题目描述

考古学家发现古代文明留下了一种奇怪的装置。该装置包含两个屏幕,分别显示两个整数 x y

经过研究,科学家对该装置得出了一个结论:该装置是一个特殊的时钟,它从过去的某个时间点开始测量经过的时刻数 t ,但该装置的创造者却将 t 用奇怪的方式显示出来。若从该装置开始测量到现在所经过的时刻数为 t ,装置会显示两个整数: x = ((t + \lfloor \frac{t}{B} \rfloor) \bmod A) ,与 y = (t \bmod B) 。这里 \lfloor x\rfloor 是下取整函数,表示小于或等于 x 的最大整数。

考古学家通过进一步研究还发现,该装置的屏幕无法一直工作。实际上,该装置的屏幕只在 n 个连续的时间区间段中能正常工作。第 i 个时间段从时刻 l_i 到时刻 r_i 。现在科学家想要知道有多少个不同的数对 (x, y) 能够在该装置工作时被显示出来。

两个数对 (x_1, y_1) (x_2, y_2) 不同当且仅当 x_1 \not = x_2 y_1 \not = y_2

输入格式

第一行包含三个整数 n, A B
接下来 n 行每行两个整数 l_i, r_i ,表示装置可以工作的第 i 个时间区间。

输出格式

输出一行一个整数表示问题的答案。

样例

样例输入 1

3 3 3
4 4
7 9
17 18

样例输出 1

4

样例说明 1

对于第一个样例,装置屏幕将显示如下这些数对。

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)

样例输入 2

3 5 10
1 20
50 68
89 98

样例输出 2

31

样例输入 3

2 16 13
2 5
18 18

样例输出 3

5

数据范围与提示

对于全部数据, 1\le n\le 10^6,1\le A,B\le 10^{18},0\le l_i\le r_i\le 10^{18},r_i<l_i+1

S=\sum\limits_{i=1}^n (r_i-l_i+1) L=\max\limits_{i=1}^n (r_i-l_i+1)

详细子任务附加限制与分值如下表。

子任务 附加限制 分值
1 S\le 10^6 10
2 n=1 5
3 A\cdot B\le 10^6
4 B=1
5 B\le 3
6 B\le 10^6 20
7 L\le B
8 无附加限制 30