APIO '19 P1 - Strange Device

View as PDF

Submit solution

Points: 20
Time limit: 1.8s
Memory limit: 512M

Problem type

Archaeologists have found a strange device that was probably created by some ancient civilization. The device has a screen that displays two integers: x and y.

After exploring the device the scientists have made a conclusion that the device is kind of a clock. It measures time t passed from some moment in the past, but shows it in some weird way, probably used by the creators of the device. If the time passed is an integer t, the two integers displayed are: x=((t+tB)modA), and y=(tmodB). Here x is the floor function — the greatest integer less or equal to x.

The archaeologists have studied the device and found out that its screen wasn't turned on all the time. Actually it was only working during n continuous periods of time, the i-th of them was from the moment li to the moment ri, inclusive. Now the scientists would like to calculate how many distinct pairs (x,y) were shown by the device when its screen was on.

Two pairs (x1,y1) and (x2,y2) are distinct if x1x2 or y1y2.

Input Specification

The first line contains three integers n, A, and B (1n106; 1A,B1018).

Each of the following n lines contains two integers li and ri, the beginning and the end of the i-th segment [li,ri] when the device screen was turned on (0liri1018; ri<li+1).

Output Specification

Output the number of distinct pairs (x,y) that were shown on the device screen when it was turned on.

Scoring

Let S=i=1n(rili+1) and L=max1in(rili+1).

Subtask 1 (points: 10)

S106

Subtask 2 (points: 5)

n=1

Subtask 3 (points: 5)

AB106

Subtask 4 (points: 5)

B=1

Subtask 5 (points: 5)

B3

Subtask 6 (points: 20)

B106

Subtask 7 (points: 20)

LB

Subtask 8 (points: 30)

No additional constraint.

Sample Input 1

Copy
3 3 3
4 4
7 9
17 18

Sample Output 1

Copy
4

Sample Input 2

Copy
3 5 10
1 20
50 68
89 98

Sample Output 2

Copy
31

Sample Input 3

Copy
2 16 13
2 5
18 18

Sample Output 3

Copy
5

Explanation

In the first test, the device screen shows the following integers.

t=4, (x,y)=(2,1)

t=7, (x,y)=(0,1)

t=8, (x,y)=(1,2)

t=9, (x,y)=(0,0)

t=17, (x,y)=(1,2)

t=18, (x,y)=(0,0)

So there are four distinct pairs (0,0), (0,1), (1,2), (2,1).


Comments


  • 4
    Aaeria  commented on Oct. 1, 2019, 6:10 p.m.

    AB1019


    • 0
      Plasmatic  commented on May 15, 2020, 2:15 a.m. edit 2

      It's actually even smaller: A×B fits inside a long long. (1019263)