#P5830. [APIO2019] 奇怪装置

[APIO2019] 奇怪装置

题目描述

考古学家发现古代文明留下了一种奇怪的装置。该装置的屏幕显示两个整数 xx 和 yy。

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

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

两个数对 (x1,y1)(x_1,y_1) 和 (x2,y2)(x_2,y_2) 不同当且仅当 x1≠x2x_1 \neq x_2 或 y1≠y2y_1 \neq y_2。

输入格式

从标准输入读入数据。第一行包含三个整数 nn,AA 与 BB。 接下来 nn 行每行两个整数 lil_i,rir_i 表示装置可以工作的第 ii 个时间区间。

输出格式

向标准输出写一个整数,表示不同数对的数量。

样例 #1

样例输入 #1

3 3 3
4 4
7 9
17 18

样例输出 #1

4

样例 #2

样例输入 #2

3 5 10
1 20
50 68
89 98

样例输出 #2

31

样例 #3

样例输入 #3

2 16 13
2 5
18 18

样例输出 #3

5

提示

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

tt (x,y)(x,y)
44 (2,1)(2,1)
77 (0,1)(0,1)
88 (1,2)(1,2)
99 (0,0)(0,0)
1717 (1,2)(1,2)
1818 (0,0)(0,0)

共有四个不同的数对:(0,0),(0,1),(1,2),(2,1)(0,0),(0,1),(1,2),(2,1)

对于全部数据,$1 \leq n \leq 10^6,1 \leq A,B \leq 10^{18},0 \leq l_i \leq r_i \leq 10^{18}$。区间按时间顺序给出,且 ri<li+1r_i<l_{i+1}(1≤i<n1\le i<n)。

令 S=∑i=1n(ri−li+1)S=\sum_{i=1}^n (r_i-l_i+1) 与 L=max⁡1≤i≤n(ri−li+1)L=\max_{1\le i\le n}(r_i-l_i+1)。

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

子任务 附加限制 分值
1 S≤106S\leq 10^6 10
2 n=1n=1 5
3 A×B≤106A\times B \leq 10^6
4 B=1B=1
5 B≤3B\leq 3
6 B≤106B\leq 10^6 20
7 L≤BL\leq B
8 无附加限制 30