loj#P3144. 「APIO2019」奇怪装置

「APIO2019」奇怪装置

题目描述

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

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

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

两个数对 (x1,y1)(x_1, y_1)(x2,y2)(x_2, y_2) 不同当且仅当 x1x2x_1 \not = x_2y1y2y_1 \not = y_2

输入格式

第一行包含三个整数 n,An, ABB
接下来 nn 行每行两个整数 li,ril_i, r_i,表示装置可以工作的第 ii 个时间区间。

输出格式

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

3 3 3
4 4
7 9
17 18
4
3 5 10
1 20
50 68
89 98
31
2 16 13
2 5
18 18
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=i=1n(rili+1)S=\sum\limits_{i=1}^n (r_i-l_i+1)L=maxi=1n(rili+1)L=\max\limits_{i=1}^n (r_i-l_i+1)

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

子任务 附加限制 分值
11 S106S\le 10^6 1010
22 n=1n=1 55
33 AB106A\cdot B\le 10^6
44 B=1B=1
55 B3B\le 3
66 B106B\le 10^6 2020
77 LBL\le B
88 无附加限制 3030