Problem Solving을 위한 가장 기초적인 정수론

0. 들어가며

우선 정수론이 뭘까요? 수학의 한 분야라는 건 알겠는데, 정수를 다루는 걸까? 맞습니다. 정수들의 여러 성질들에 대해서 연구하는 학문입니다. 깊이 들어가면 현대 수학에서는 해석적 정수론이나 대수적 정수론적인 방법론으로 접근해서 문제를 푸는 경우가 아주 많고, 그렇기에 저 두 분야에 대한 간략한 이해도 상당히 필요하지만 우선은 수학 글이 아니라 PS 글이니까 이건 넘기도록 하겠습니다.

 

정말 간단하게 정수론에서 다루는 문제의 예시를 들면, 다음과 같은 것들이 있습니다.

 

어떤 수를 어떻게 하면 소인수분해를 빠르게 할 수 있는가?

어떤 수가 소수인 걸 어떻게 빠르게 알 수 있는가?
어떤 방정식의 정수 해들을 어떻게 빠르게 구할 수 있는가?

 

정말로 재미 없는 수학문제들 같아 보이지만, 정수론은 의외로 PS에서 한 부분을 당당히 차지하고 있는 분야입니다. 이게 왜 들어가있나? 싶을 수 있겠지만, 실제로 정수론의 많은 문제들은 컴퓨터 과학의 힘을 빌리고 있고, 컴퓨터 과학 또한 상당 부분 정수론의 힘을 빌리고 있습니다. 요컨대 상부상조하는 사이인 거죠.

 

PS에서의 정수론에 대한 설명을 하고 있는 글들은 이미 여러 사이트들에 많이 올라와 있습니다. 저 또한 그런 글들의 도움을 많이 받으면서 공부해 나갔고요. 하지만, 저는 중학교 때 중등 KMO를 했었기도 하고, 애초에 수학과이기 때문에 상당한 배경지식이 있는 상태에서 시작했고, 정말로 페르마 소정리는 커녕 mod가 뭔지, 아니 그 이전에 약수 개수 구하는 공식도 잊어버린 상태에서 PS를 시작하시는 분들도 많으시리라 생각합니다. 이 글은 그렇게 정수론의 세계에 첫 발을 내딛은 사람들에게 조금이나마 도움이 되고자 작성되었습니다.

 

Möbius inversion formula니 Xudyh's Sieve니 하는 것들이 solved.ac 기준 다이아-루비 정수론 문제들에서 간혹 나오지만, 이런 글들을 쓰려는 것이 아닐뿐더러, 저보다도 훨씬 잘 설명하시는 분들이 많습니다.

1. 합동식? Modulo?

여기저기 정수론 문제 풀이를 보거나, 아니면 이쪽 바닥의 수학 좋아하는 사람들의 대화를 듣다 보면

아니면 KMO를 준비하는 대치 키즈의 대화를 듣게되면

 간혹 mod가 어쩌니, mod n에서 저쩌니, 하는 이야기를 하는 것들을 들을 수 있습니다. 도대체 이 mod가 뭘까요? 이런 mod가 들어가는 식을 우리는 합동식이라고 부릅니다.

a ≡ b (mod m)

도대체 무슨 뜻일까요? 이건 a를 m으로 나눈 나머지랑 b를 m으로 나눈 나머지가 같다는 뜻입니다. 잘 이해가 가지 않으신다면, 달력을 생각해보실 수 있겠네요.

벌써 12월이라니...

이쪽은 2022년 12월 달력입니다. 1주일은 무슨 일이 있어도 언제나 7일이니까, 오늘 1일이 목요일이었다면 다음주 8일도 목요일이고, 그 다음주의 15일도 목요일, 그그 다음주의 22일도 목요일... 이런 식으로 반복됩니다. 7씩 더해나가도 계속 같은 요일이 되는 거죠. 갑자기 1일이 목요일인데 8일이 금요일이 되는 등의 일은(적어도 16세기 이후로는)웬만해선 없습니다.

 

이 1일, 8일, 15일, 22일, 29일...들. 그러니까 목요일이 되는 날들의 공통점이 보이시나요? 1에서부터 7을 더하면서 시작했기 때문에 7로 나눈 나머지가 모두 1입니다! 그러니까 달력에서 세로줄은 7로 나눈 나머지가 같은 숫자들이 모여 있다고 할 수 있겠죠.

 

그런데 제가 오늘 날짜는 그렇게 궁금하지 않고, 오늘이 무슨 요일인지만 궁금하다고 해봅시다. 그렇다면 1일이나 8일이나 29일이나, 제게는 똑같은 목요일입니다. 숫자 자체는 알 바가 아니고, 요일만 중요한 상황인거죠. 마찬가지로 어떤 숫자 그 자체보다는 그 수로 나눈 나머지만이 중요한 상황에서 주로 사용되는 것이 바로 이 합동식입니다.

 

그렇다면, 다시 달력으로 돌아가서 1일과 29일이 같은 요일이라는 것을 수학적으로 적고 싶다! 라고 한다면, 우리는 다음과 같이 적을 수 있습니다.

1 ≡ 29 (mod  7)

눈치가 빠르신 분들이라면, 1과 29만이 아니라 8도, 15도, 22도, -6도, 혹은 -1000같은 어처구니 없는 숫자들도 모두 1과 mod 7에서 같다는 것을 알 수 있습니다.

 

그래서 이 mod는 왜 언급했느냐? 의외로 이 개념은 깊이 파고 들어가야 하는 수학 문제가 아닌, 일반적인 문제에서도 꽤 유용하기 때문입니다. 아마 PS를 조금 하셨더라면, 다음과 같은 문장을 많이 보신 적이 있을 겁니다.

"값이 매우 클 수 있으니 998244353으로 나눈 나머지를 출력하도록 한다."

 

998244353은 소수로, FFT(모르신다면 넘어가셔도 괜찮습니다.)를 할 때 원시근이 작고 C 계열 언어의 int 자료형의 한계 안에 들어가기 때문에 많이 애용되곤 합니다. 이런 문장 자체는 그다지 수학과 관련 없어 보이는 문제들(dp 문제, 자료구조 문제 등등)에서도 많이 나옵니다.

 

이런 문제를 볼 때 종종 많이 하시는 실수가 값을 먼저 다 구해두고 주어진 소수(998244353이나, 1000000007 등등)로 나눈 나머지를 마지막에 구하는 겁니다. C 계열 언어들이었으면 오버플로우로 이상한 숫자를 볼 것이고, Python과 같이 오버플로우 걱정이 없는 언어라도 숫자가 너무 커지면 계산하는 시간이 많아서 안그래도 느린 Python이 TLE가 뜨는 사태가 벌어집니다. 그럼 도대체 어떻게 해야 할까요?

 

여기서 합동식의 중요한 성질이 나옵니다. 합동식 기호를 사용하면, 덧셈, 뺄셈, 곱셈, 거듭제곱과 같이 우리가 아는 웬만한 연산들이 그대로 보존됩니다.(*나눗셈은 아닙니다.)이게 무슨 뜻인가 하면 어떤 두 정수 a≡b(mod n)을 만족한다면 어떤 임의의 정수 k에 대해서

 

a+k ≡ b+k (mod n)

a−k ≡ b−k (mod n)

ak ≡ bk (mod n)

a^k ≡ b^k (mod n)

 

가 모두 성립한다는 뜻입니다.

 

다시 말해서, 어떤 값들을 더하거나, 곱하거나, 거듭제곱하는 연산들을 한다면 998244353으로 나눈 나머지를 끝나고 나서 계산하나, 과정 중간중간에 계산하나 똑같다는 뜻입니다. 증명은 따로 설명하지는 않도록 하겠습니다.

 

이렇게 합동식의 성질을 사용하면서 계산하면 C++에서 오버플로가 날 걱정도, Python에서 시간을 많이 잡아먹을 걱정도 안하셔도 됩니다.(다만 저게 나올 정도의 문제면 과정에서 이미 너무 큰 수가 나올 수 있으니까 C++은 웬만해선 long long int로 선언하시는 걸 권장드립니다.)

2. 빠른 거듭제곱?

조금 더 나아가서는, 거듭제곱 한 수를 특정한 소수로 나눈 값을 구하라는 문제 또한 많이 있습니다. 이 때, x의 n제곱과 같은 걸 계산할 때, 이런 실수를 하시는 경우가 아주 많습니다.

 

"그냥 for문 돌려서 n제곱 하고, 곱하면서 각각 998244353으로 나눈 나머지로 만들어주면 되는 거 아니야?"

 

하지만 이 거듭제곱은 O(n)의 시간이 걸리고, 지수 위로 1e18같은 숫자가 나타난다면 속절없이 무너지게 됩니다.

 

엥? 거듭제곱에 O(n)보다 더 빠른 시간을 쓸 수 있을까요? 이렇게 큰 숫자의 거듭제곱을 하기 위해서 분할 정복이라는 테크닉을 주로 사용하곤 합니다. 재귀 함수/메모이제이션에 대한 사전 지식이 없으시다면 이 부분은 건너뛰셔도 됩니다.

 

간략하게 요약하자면, x의 n제곱을 직접 구하는 대신, x의 n/2제곱을 구하고, 그걸 제곱하는 식으로 재귀적으로, 나오는 값들을 메모이제이션 하면서 실행하는 함수를 만들면 됩니다. Python 코드는 다음과 같겠네요.

mem = dict()
def pow(x,n,mod):
	#x^n을 mod로 나눈 나머지를 구한다.
    if n in mem:return mem[n]
    if n==0:
    	mem[n]=1
        return 1
    half = n//2
    if n%2 == 0:
    	result = (pow(x, half, mod)**2)%mod
    else:
    	result = (pow(x, half, mod)**2*x)%mod
    mem[n] = result
    return result

사실은, Python에서 정확히 같은 기능을 하는 pow라는 내장 함수가 이미 있기 때문에, Python을 사용하신다면 이걸 구태어 다시 구현할 필요는 없습니다. 이렇게 하면 n제곱을 O(logn)정도의 시간에 끝낼 수 있습니다.

3. 엥? 분수를 갑자기 모듈러로 어쩌고 나타내라는데요??

간혹 PS 문제를 보다보면, 다음과 같은 식으로 출력 형식을 나타낼 때가 있습니다.

boj.kr/23675, 저도 안 풀어본 문제입니다. 그냥 찾아서 바로 나온 게 이거였네요.

이게 도당체 무슨 소리일까요? 기약분수 p/q로 나타내라는 것까지는 좋은데, 어떤 x에 대해서 xq-p가 998244353으로 나누어 떨어지게 하는 x를 출력하라고요? 이걸 도대체 어떻게 하면 될까요?

 

사실은, 이건 마치 수학 모의고사에서 "기약분수 p/q로 나타내었을 때, p+q의 값은?"하고 문제를 내는 것과 별반 다르지 않습니다. 표현이 조금 더 거칠어(?)진 거죠.

 

우리가 구하고 싶은 수 x는 다음과 같은 성질을 만족합니다.

 

qx ≡ p (mod 998244353)

 

마음 같아서는 그냥 p/q라고 적고 싶지만, 합동식을 정수에 대해서만 정의하고 있어서 불가능합니다. 합동식은 덧셈, 뺄셈, 곱셈은 다 마음대로 해도 된다면서, 왜 나눗셈은 안된다고 하는 걸까요? 다음과 같은 예를 봅시다.

 

3x≡1 (mod 4)

 

를 만족하는 정수 x의 값은 어떻게 될까요? 1/3이라고 본능적으로 말하고 싶지만 이건 정수론 문제입니다. 정답은 4k+3의 꼴로 나타내어질 수 있는 모든 정수들입니다. 직접 3배를 해보시면 알 수 있습니다.

 

이건 그렇게 끼워 맞춰서 풀었다 쳐도, 이걸 대체 mod 998244353에 대해서 할 수는 있는 걸까요? 다 해보는데 O(998244353)인데요? 우린 정말 망한 걸까요?

 

그렇지 않습니다. 페르마 소정리라는 어떤 좋은 정리에 따라서, 우리는 다음과 같은 결과를 사용할 수 있습니다.

 

qx ≡ p (mod 998244353)를 만족하는 x는 p*q^(998244353-2)가 된다.

 

이 식은 998244353뿐만이 아닌 모든 소수에 대해서(q가 그 수와 서로소라면)성립합니다. 보통은 실제 문제에서는 저걸 998244353으로 나눈 나머지를 묻곤 합니다. 이게 어떻게 가능한지에 대한 자세한 설명은 이 글에서 목표하는 레벨을 조금 벗어난 것 같으니 설명은 생략하고, 후에 다른 글에서 기회가 된다면 언급하겠습니다.

 

여하튼, 대강 10억제곱을 하는 것도 위에서 말한 거듭제곱을 사용하면 그렇게 문제가 되지 않고, 저걸 구하기만 하면 됩니다. Python 기준으로 x를 구하는 함수를 작성하면 다음과 같습니다.

mod = 998244353
def solve(p, q):
    #p/q에 대해서, qx와 p가 합동인 x 찾기
    x = p * pow(q, mod-2, mod)
    return x%mod

마지막으로 짚고 넘어갈 부분이 있다면, 저러한 문제는 종종 분수의 분자나 분모가 급격히 커질 수 있습니다. 이 값들 또한 나중에 998244353으로 나누나, 진행 과정에서 나눈 나머지를 사용하나 결과값을 똑같습니다. 따라서 과정 중간중간에 분자와 분모를 주어진 소수로 나눈 나머지로 바꾸는 작업을 하는 것이 훨씬 빠르게 해결될 때가 많습니다.

 

지금까지 ps에서 필요한/사용하면 좋은 합동식의 간단한 성질들을 알아보았습니다. 사실 저는 이 내용들을 공부한지가 꽤 되어서, 어떻게 설명해야 노 베이스인 사람에게도 어렵지 않을까 고민을 많이 했네요. 혹시 어려운 부분이나 궁금한 점이 있으시다면 언제든 댓글로 물어봐주시면 제가 아는 한에서 답변해 드리겠습니다!