파이썬을 사용하여 정수론 관련 문제를 풀 때 빠르게 참고할 사항만 정리해두었다.

소수 모듈러 역원

문제의 답을 10^9+7 같은 소수로 나눈 나머지를 구하는 문제가 있다.
이때 MOD 상수를 선언해준 뒤 곱연산을 수행할 때마다 MOD로 나눠줘야 한다.

그러나 나눗셈 연산을 수행하면 MOD 수행 후 값이 달라지게 된다. 2로 나눠도 안된다.
이때 모듈러 역원을 곱하면 된다.

모듈러 역원을 구하는 파이썬 식은 아래와 같다.

pow(나눌 수, -1, MOD)

예를 들어, res//=2; res%=MOD; 를 수행하는 것 대신
res=pow(2,-1,MOD); res%=MOD; 를 수행해야 한다.

원래 구하기 복잡한 과정을 거쳐야 하나, 파이썬은 그런거 없다.

nCr 함수

파이썬에서 기본 제공해주는 라이브러리 math에서 다음과 같이 사용 가능하다.

math.comb(n,r)

이외에도 올림(ceil), 버림(floor), 팩토리얼(factorial), nPr(perm) 등 다양한 함수를 가진다. 속도도 빠르니 자주 애용하자.
참고 사이트

소수 판정 함수

소수가 많이 필요하진 않다면, 아래 함수를 사용하면 된다.

def is_prime(n):
    if n<2:
        return False
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False
    return True

2부터 n의 제곱근까지 나눠서 안떨어지면 소수이다.

그러나 필요한 소수의 범위가 넓다면, 소수를 원소로 가지는 리스트를 만드는 함수를 사용한다. 이때 에라토스테네스의 체를 사용한다.

def prime_list(n):
    sieve = [True] * n
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:
            for j in range(i*i, n, i):
                sieve[j] = False
    return [i for i in range(2, n) if sieve[i] == True]

n짜리 리스트 sieve를 만든 뒤, 2부터 n의 제곱근까지의 배수를 인덱스로 가지는 원소를 False로 변환한다. 이때, 현재 원소가 True(소수)일 때만 하위 for문을 실행한다. 하위 for문의 배수는 2xi부터 i씩 증가하면서 올라가야 한다.

최대공약수

+유클리드 호제법

일단, GCD, LCM 구하는 함수는 import math로 사용할 수 있다. 원소도 여러 개 받을 수 있어 편리하다.

각설하고, 유클리드 호제법 사용하는 건 아는게 좋다.
두 수의 GCD를 구하는 방법으로, 큰 수를 작은 수로 나눈 나머지로 변환하는 것을 반복하여 최종적으로 나머지가 0이 될 때 작은 수가 GCD가 된다.

결론은 파이썬으로 GCD 구할 때 math.gcd()

소세지 자르는 문제가 대표적인 GCD 문제이다.
음식 평론가

범위 처리

파이썬은 overflow 생각은 할 필요 없지만, 정수론 특성상 범위를 크게 주는 경우가 많으므로 넉넉하게 처리하고 print로 check하는 습관을 길들이는 것이 중요하다.
prime number list가 잘 만들어졌는지, 뒷부분은 잘 처리되었는지 체크한다.

다만, 문제 풀이 전 범위 확인은 필수이다. 10^6 이상부터는 상수로 선언한 뒤 사용을 하는 습관을 길들이고, 10^100 등 터무니없이 큰 수에 대해서는 반복 index 대신 다른 방법을 생각해내는 것이 중요하다.