고고학자들은 고대 문명이 남긴 이상한 기계를 발견하였다.

이 기계는 두 정수 x와 y를 출력하는 두 부분이 있다.

이 기계를 조사해보고, 고고학자들은 이 기계가 과거의 어느 시점부터 시작하여

시점 t에 대한 정보를 출력 하는 특별한 시계라는 결론을 내렸다.

시점 t에서 첫 번째 출력 부분에서는 정수 x = ((t + [t/B] ) mod A)를 출력하고,

두번째 출력 부분에서는 정수 y = (t mod B)를 출력한다.

([x]는 x 이하이면서 가장 큰 정수를 나타낸다. X mod Y는 X를 Y로 나눈 나머지를 나타낸다.)

분석을 해 보니 이 기계가 항상 동작하는 것은 아니며,

n개의 연속된 구간 [l_i, r_i]에서만 동작하는 것을 알게 되었다.

향후 연구를 위해서, 고고학자들은 당신에게 이 기계가 출력하는 순서쌍 (x, y) 중

서로 다른 것이 모두 몇 개인지를 알아내는 프로그램을 작성하도록 부탁했다.

두 순서쌍 (x₁, y₁)와 (x₂, y₂)는 만약 x₁ ≠ x₂이거나 y₁ ≠ y₂이라면 서로 다르다.

이상한 기계 timer 4s memory 512MB

이상한 기계 4s 512MB