백준 17634 - 이상한 기계 [Python]

https://www.acmicpc.net/problem/17634

17634번: 이상한 기계

[사용한 알고리즘]

라인 스위핑, 정수론

 

greedev에게 APIO 문제를 추천해달라고 해서 받은 문제다.

 

 

간단하고 재미있는 식정리이다.

 

\(t = Bp + q\) (p, q 서로소 아님) 으로 두면,

\(x = ((B + 1)p + q) \hspace{0.15cm} mod \hspace{0.15cm} A\)

\(y = q\)

가 된다.

 

\(q = 0\)으로 두면,

\(x\)의 주기는 \(\frac{A}{gcd(A, B + 1)}\)이고,

\(y\)의 주기는 \(B\)이다.

이 둘을 곱한 값인 \(\frac{AB}{gcd(A, B + 1)}\)가 순서쌍의 주기이므로, 주기를 \(m\)이라고 할 때 \(t \hspace{0.15cm} mod \hspace{0.15cm} m\)의 서로 다른 값의 개수를 찾으면 된다.

 

\([l, r]\)을 \([l \hspace{0.15cm} mod \hspace{0.15cm} m, r \hspace{0.15cm} mod \hspace{0.15cm} m]\)으로 바꾸고 라인스위핑을 하면 끝이다.

 

74줄부터 보면 된다.

import sys, math
import heapq
 
from dataclasses import dataclass
from collections import deque
from bisect import bisect_left, bisect_right
 
input = sys.stdin.readline
 
hqp = heapq.heappop
hqs = heapq.heappush
 
 
# input
def ip(): return int(input())
def sp(): return str(input().rstrip())
 
def mip(): return map(int, input().split())
def msp(): return map(str, input().split().rstrip())
 
def lmip(): return list(map(int, input().split()))
def lmsp(): return list(map(str, input().split()))
 
 
# gcd, lcm
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x
 
 
def lcm(x, y):
    return x * y // gcd(x, y)
 
 
# prime
def isPrime(x):
    if x <= 1: return False
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            return False
    return True
 
 
# Union Find
# p = [i for i in range(n + 1)]
 
def find(x):
    if x == p[x]:
        return x
    q = find(p[x])
    p[x] = q
    return q
 
 
def union(x, y):
    x = find(x)
    y = find(y)
 
    if x != y:
        p[y] = x
 
 
def getPow(a, x):
    ret = 1
    while x:
        if x & 1:
            ret = (ret * a) % MOD
        a = (a * a) % MOD
        x >>= 1
    return ret
 
 
############### Main! ###############
 
n, A, B = mip()
m = A // gcd(A, B + 1) * B
a = []
for i in range(n):
    l, r = mip()
    if r - l >= m:
        print(m)
        exit()
 
    if l % m > r % m:
        a.append([l % m, m - 1])
        a.append([0, r % m])
    else:
        a.append([l % m, r % m])
a.sort()
ans = 0
l = a[0][0]
r = a[0][1]
for i in range(1, len(a)):
    nl = a[i][0]
    nr = a[i][1]
    if l <= nl and nr <= r:
        continue
    if r < nl:
        ans += r - l + 1
        l = nl
    r = nr
ans += r - l + 1
print(ans)
 
 
######## Priest greedev ########