시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 42 12 12 36.364%

문제

고고학자들은 고대 문명이 남긴 이상한 기계를 발견하였다. 이 기계는 두 정수 x와 y를 출력하는 두 부분이 있다.

이 기계를 조사해보고, 고고학자들은 이 기계가 과거의 어느 시점부터 시작하여 시점 t에 대한 정보를 출력 하는 특별한 시계라는 결론을 내렸다. 시점 T에서 첫 번째 출력 부분에서는 정수 x = ((t + ⌊t/B⌋ ) mod A)를 출력하고, 두번째 출력 부분에서는 정수 y = (t mod B)를 출력한다. (⌊x⌋는 x 이하이면서 가장 큰 정수를 나타낸다.)

분석을 해 보니 이 기계가 항상 동작하는 것은 아니며, n개의 연속된 구간 [li, ri]에서만 동작하는 것을 알게 되었다. 향후 연구를 위해서, 고고학자들은 당신에게 이 기계가 출력하는 순서쌍 (x, y) 중 서로 다른 것이 모두 몇 개인지를 알아내는 프로그램을 작성하도록 부탁했다.

두 순서쌍 (x1, y1)와 (x2, y2)는 만약 x1 ≠ x2이거나 y1 ≠ y2이라면 서로 다르다.

입력

첫 줄에는 세 정수 n, A, B가 주어진다. (1 ≤ n ≤ 106; 1 ≤ A, B ≤ 1018).

다음 n줄의 각각에는 두 정수 li와 ri가 주어지는데, 이 기계가 동작하는 구간 [li, ri]의 시작 시점과 종료 시점을 나타낸다. (0 ≤ li ≤ ri ≤ 1018 , ri < li+1).

출력

이 기계가 동작하는 동안 출력하는 서로 다른 순서쌍 (x, y)의 수를 출력한다.

예제 입력 1

3 3 3
4 4
7 9
17 18

예제 출력 1

4

예제 입력 2

3 5 10
1 20
50 68
89 98

예제 출력 2

31

예제 입력 3

2 16 13
2 5
18 18

예제 출력 3

5

힌트

첫 번째 테스트에서, 이 기계는 시점 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)을 출력한다.

W3sicHJvYmxlbV9pZCI6IjE3NjM0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNzc0XHVjMGMxXHVkNTVjIFx1YWUzMFx1YWNjNCIsImRlc2NyaXB0aW9uIjoiPHA+XHVhY2UwXHVhY2UwXHVkNTU5XHVjNzkwXHViNGU0XHVjNzQwIFx1YWNlMFx1YjMwMCBcdWJiMzhcdWJhODVcdWM3NzQgXHViMGE4XHVhZTM0IFx1Yzc3NFx1YzBjMVx1ZDU1YyBcdWFlMzBcdWFjYzRcdWI5N2MgXHViYzFjXHVhY2FjXHVkNTU4XHVjNjAwXHViMmU0LiBcdWM3NzQgXHVhZTMwXHVhY2M0XHViMjk0IFx1YjQ1MCBcdWM4MTVcdWMyMTggeFx1YzY0MCB5XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWI0NTAgXHViZDgwXHViZDg0XHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YWUzMFx1YWNjNFx1Yjk3YyBcdWM4NzBcdWMwYWNcdWQ1NzRcdWJjZjRcdWFjZTAsIFx1YWNlMFx1YWNlMFx1ZDU1OVx1Yzc5MFx1YjRlNFx1Yzc0MCBcdWM3NzQgXHVhZTMwXHVhY2M0XHVhYzAwIFx1YWNmY1x1YWM3MFx1Yzc1OCBcdWM1YjRcdWIyOTAgXHVjMmRjXHVjODEwXHViZDgwXHVkMTMwIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YzVlYyBcdWMyZGNcdWM4MTAgdFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHViOTdjIFx1Y2Q5Y1x1YjgyNSBcdWQ1NThcdWIyOTQgXHVkMmI5XHViY2M0XHVkNTVjIFx1YzJkY1x1YWNjNFx1Yjc3Y1x1YjI5NCBcdWFjYjBcdWI4NjBcdWM3NDQgXHViMGI0XHViODM4XHViMmU0LiBcdWMyZGNcdWM4MTAgVFx1YzVkMFx1YzExYyBcdWNjYWIgXHViYzg4XHVjOWY4IFx1Y2Q5Y1x1YjgyNSBcdWJkODBcdWJkODRcdWM1ZDBcdWMxMWNcdWIyOTQgXHVjODE1XHVjMjE4IHggPSAoKHQgKyAmbGZsb29yO3RcL0ImcmZsb29yOyApIG1vZCBBKVx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsIFx1YjQ1MFx1YmM4OFx1YzlmOCBcdWNkOWNcdWI4MjUgXHViZDgwXHViZDg0XHVjNWQwXHVjMTFjXHViMjk0IFx1YzgxNVx1YzIxOCB5ID0gKHQgbW9kIEIpXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gKCZsZmxvb3I7eCZyZmxvb3I7XHViMjk0IHggXHVjNzc0XHVkNTU4XHVjNzc0XHViYTc0XHVjMTFjIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVjODE1XHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4pPFwvcD5cclxuXHJcbjxwPlx1YmQ4NFx1YzExZFx1Yzc0NCBcdWQ1NzQgXHViY2Y0XHViMmM4IFx1Yzc3NCBcdWFlMzBcdWFjYzRcdWFjMDAgXHVkNTZkXHVjMGMxIFx1YjNkOVx1Yzc5MVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDAgXHVjNTQ0XHViMmM4XHViYTcwLCBuXHVhYzFjXHVjNzU4IFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWFkNmNcdWFjMDQgW2w8c3ViPmk8XC9zdWI+LCByPHN1Yj5pPFwvc3ViPl1cdWM1ZDBcdWMxMWNcdWI5Y2MgXHViM2Q5XHVjNzkxXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM1NGNcdWFjOGMgXHViNDE4XHVjNWM4XHViMmU0LiBcdWQ1YTVcdWQ2YzQgXHVjNWYwXHVhZDZjXHViOTdjIFx1YzcwNFx1ZDU3NFx1YzExYywgXHVhY2UwXHVhY2UwXHVkNTU5XHVjNzkwXHViNGU0XHVjNzQwIFx1YjJmOVx1YzJlMFx1YzVkMFx1YWM4YyBcdWM3NzQgXHVhZTMwXHVhY2M0XHVhYzAwIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWMzMGQgKHgsIHkpIFx1YzkxMSBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YWM4M1x1Yzc3NCBcdWJhYThcdWI0NTAgXHViYTg3IFx1YWMxY1x1Yzc3OFx1YzljMFx1Yjk3YyBcdWM1NGNcdWM1NDRcdWIwYjRcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWJkODBcdWQwYzFcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWMyMWNcdWMxMWNcdWMzMGQgKHg8c3ViPjE8XC9zdWI+LCB5PHN1Yj4xPFwvc3ViPilcdWM2NDAgKHg8c3ViPjI8XC9zdWI+LCB5PHN1Yj4yPFwvc3ViPilcdWIyOTQgXHViOWNjXHVjNTdkIHg8c3ViPjE8XC9zdWI+ICZuZTsmbmJzcDt4PHN1Yj4yPFwvc3ViPlx1Yzc3NFx1YWM3MFx1YjA5OCB5PHN1Yj4xPFwvc3ViPiAmbmU7Jm5ic3A7eTxzdWI+MjxcL3N1Yj5cdWM3NzRcdWI3N2NcdWJhNzQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMTM4IFx1YzgxNVx1YzIxOCBuLCBBLCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBuICZsZTsgMTA8c3VwPjY8XC9zdXA+OyAxICZsZTsgQSwgQiAmbGU7IDEwPHN1cD4xODxcL3N1cD4pLjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgblx1YzkwNFx1Yzc1OCBcdWFjMDFcdWFjMDFcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCBsPHN1Yj5pPFwvc3ViPlx1YzY0MCByPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTRcdWIzNzAsIFx1Yzc3NCBcdWFlMzBcdWFjYzRcdWFjMDAgXHViM2Q5XHVjNzkxXHVkNTU4XHViMjk0IFx1YWQ2Y1x1YWMwNCBbbDxzdWI+aTxcL3N1Yj4sIHI8c3ViPmk8XC9zdWI+XVx1Yzc1OCBcdWMyZGNcdWM3OTEgXHVjMmRjXHVjODEwXHVhY2ZjIFx1Yzg4NVx1YjhjYyBcdWMyZGNcdWM4MTBcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiAoMCAmbGU7IGw8c3ViPmk8XC9zdWI+ICZsZTsgcjxzdWI+aTxcL3N1Yj4gJmxlOyAxMDxzdXA+MTg8XC9zdXA+ICwgcjxzdWI+aTxcL3N1Yj4gJmx0OyBsPHN1Yj5pKzE8XC9zdWI+KS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM3NzQgXHVhZTMwXHVhY2M0XHVhYzAwIFx1YjNkOVx1Yzc5MVx1ZDU1OFx1YjI5NCBcdWIzZDlcdWM1NDggXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMjFjXHVjMTFjXHVjMzBkICh4LCB5KVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1YzVkMFx1YzExYywgXHVjNzc0IFx1YWUzMFx1YWNjNFx1YjI5NCBcdWMyZGNcdWM4MTAgNFx1YzVkMFx1YzExYyAoMiwgMSlcdWM3NDQsIFx1YzJkY1x1YzgxMCA3XHVjNWQwXHVjMTFjICgwLCAxKVx1Yzc0NCwgXHVjMmRjXHVjODEwIDhcdWM1ZDBcdWMxMWMgKDEsIDIpXHViOTdjLCBcdWMyZGNcdWM4MTAgOSBcdWM1ZDBcdWMxMWMgKDAsIDApXHViOTdjLCBcdWMyZGNcdWM4MTAgMTdcdWM1ZDBcdWMxMWMgKDEsIDIpXHViOTdjLCBcdWMyZGNcdWM4MTAgMThcdWM1ZDBcdWMxMWMgKDAsIDApXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViMTI0IFx1YWMxY1x1Yzc1OCBcdWMyMWNcdWMxMWNcdWMzMGQgKDAsIDApLCgwLCAxKSwoMSwgMiksKDIsIDEpXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE3NjM0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3RyYW5nZSBEZXZpY2UiLCJkZXNjcmlwdGlvbiI6IjxwPkFyY2hhZW9sb2dpc3RzIGhhdmUgZm91bmQgYSBzdHJhbmdlIGRldmljZSB0aGF0IHdhcyBwcm9iYWJseSBjcmVhdGVkIGJ5IHNvbWUgYW5jaWVudCBjaXZpbGl6YXRpb24uIFRoZSBkZXZpY2UgaGFzIGEgc2NyZWVuIHRoYXQgZGlzcGxheXMgdHdvIGludGVnZXJzOiB4IGFuZCB5LjxcL3A+XHJcblxyXG48cD5BZnRlciBleHBsb3JpbmcgdGhlIGRldmljZSB0aGUgc2NpZW50aXN0cyBoYXZlIG1hZGUgYSBjb25jbHVzaW9uIHRoYXQgdGhlIGRldmljZSBpcyBraW5kIG9mIGEgY2xvY2suIEl0IG1lYXN1cmVzIHRpbWUgdCBwYXNzZWQgZnJvbSBzb21lIG1vbWVudCBpbiB0aGUgcGFzdCwgYnV0IHNob3dzIGl0IGluIHNvbWUgd2VpcmQgd2F5LCBwcm9iYWJseSB1c2VkIGJ5IHRoZSBjcmVhdG9ycyBvZiB0aGUgZGV2aWNlLiBJZiB0aGUgdGltZSBwYXNzZWQgaXMgYW4gaW50ZWdlciB0LCB0aGUgdHdvIGludGVnZXJzIGRpc3BsYXllZCBhcmU6IHggPSAoKHQgKyAmbGZsb29yO3RcL0ImcmZsb29yOyApIG1vZCBBKSwgYW5kIHkgPSAodCBtb2QgQikuIEhlcmUgJmxmbG9vcjt4JnJmbG9vcjsgaXMgdGhlIGZsb29yIGZ1bmN0aW9uICZtZGFzaDsgdGhlIGdyZWF0ZXN0IGludGVnZXIgbGVzcyBvciBlcXVhbCB0byB4LjxcL3A+XHJcblxyXG48cD5UaGUgYXJjaGFlb2xvZ2lzdHMgaGF2ZSBzdHVkaWVkIHRoZSBkZXZpY2UgYW5kIGZvdW5kIG91dCB0aGF0IGl0cyBzY3JlZW4gd2FzbiZyc3F1bzt0IHR1cm5lZCBvbiBhbGwgdGhlIHRpbWUuIEFjdHVhbGx5IGl0IHdhcyBvbmx5IHdvcmtpbmcgZHVyaW5nIG4gY29udGludW91cyBwZXJpb2RzIG9mIHRpbWUsIHRoZSBpLXRoIG9mIHRoZW0gd2FzIGZyb20gdGhlIG1vbWVudCBsPHN1Yj5pPFwvc3ViPiB0byB0aGUgbW9tZW50IHI8c3ViPmk8XC9zdWI+LCBpbmNsdXNpdmUuIE5vdyB0aGUgc2NpZW50aXN0cyB3b3VsZCBsaWtlIHRvIGNhbGN1bGF0ZSBob3cgbWFueSBkaXN0aW5jdCBwYWlycyAoeCwgeSkgd2VyZSBzaG93biBieSB0aGUgZGV2aWNlIHdoZW4gaXRzIHNjcmVlbiB3YXMgb24uPFwvcD5cclxuXHJcbjxwPlR3byBwYWlycyAoeDxzdWI+MTxcL3N1Yj4sIHk8c3ViPjE8XC9zdWI+KSBhbmQgKHg8c3ViPjI8XC9zdWI+LCB5PHN1Yj4yPFwvc3ViPikgYXJlIGRpc3RpbmN0IGlmIHg8c3ViPjE8XC9zdWI+ICZuZTsgeDxzdWI+MjxcL3N1Yj4gb3IgeTxzdWI+MTxcL3N1Yj4gJm5lOyB5PHN1Yj4yPFwvc3ViPi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRocmVlIGludGVnZXJzIG4sIEEsIGFuZCBCICgxICZsZTsgbiAmbGU7IDEwPHN1cD42PFwvc3VwPjsgMSAmbGU7IEEsIEIgJmxlOyAxMDxzdXA+MTg8XC9zdXA+KS48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIG4gbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzIGw8c3ViPmk8XC9zdWI+IGFuZCByPHN1Yj5pPFwvc3ViPiwgdGhlIGJlZ2lubmluZyBhbmQgdGhlIGVuZCBvZiB0aGUgaS10aCBzZWdtZW50IFtsPHN1Yj5pPFwvc3ViPiwgcjxzdWI+aTxcL3N1Yj5dIHdoZW4gdGhlIGRldmljZSBzY3JlZW4gd2FzIHR1cm5lZCBvbiAoMCAmbGU7IGw8c3ViPmk8XC9zdWI+ICZsZTsgcjxzdWI+aTxcL3N1Yj4gJmxlOyAxMDxzdXA+MTg8XC9zdXA+OyByPHN1Yj5pPFwvc3ViPiAmbHQ7IGw8c3ViPmkrMTxcL3N1Yj4pLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbnVtYmVyIG9mIGRpc3RpbmN0IHBhaXJzICh4LCB5KSB0aGF0IHdlcmUgc2hvd24gb24gdGhlIGRldmljZSBzY3JlZW4gd2hlbiBpdCB3YXMgdHVybmVkIG9uLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5JbiB0aGUgZmlyc3QgdGVzdCwgdGhlIGRldmljZSBzY3JlZW4gc2hvd3MgdGhlIGZvbGxvd2luZyBpbnRlZ2Vycy48XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOjIwJTtcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj50PFwvdGg+XHJcblx0XHRcdDx0aCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj4oeCwgeSk8XC90aD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjQ8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPigyLCAxKTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj43PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj4oMCwgMSk8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+ODxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+KDEsIDIpPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjk8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPigwLCAwKTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj4xNzxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+KDEsIDIpPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjE4PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj4oMCwgMCk8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPlNvIHRoZXJlIGFyZSBmb3VyIGRpc3RpbmN0IHBhaXJzICgwLCAwKSwoMCwgMSksKDEsIDIpLCgyLCAxKS48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Asia-Pacific Informatics Olympiad > APIO 2019 A번