garam1732's profile image

garam1732

December 25, 2023 17:00

https://www.acmicpc.net/category/detail/4072

해당 링크는 12월 3일에서 12월 10일까지 열렸던 BOJ Bundle이라는 백준 커뮤니티 대회이다. 이번 글에서는 대회에 사용되었던 정수론 테크닉들을 몇 개 소개해보려 한다.

F. Queens’ Rye Cafe

요약: 분모가 $N$이하인 $[0, 1]$의 기약분수들을 정렬하였을 때, $a/b$의 $j$번째 다음 항을 구해야 한다.

Farey Sequence의 성질을 이용하는 문제이다. 특히 이번 ICPC 2023 예선 G에 출제되면서 더욱 유명해진 것 같다.

Farey Sequence란 정렬된 기약분수의 수열을 생성하는 방법이다. 기본적으로 두 기약분수 $(0/1, 1/1)$에서 시작한다. 매 차례마다 두 기약분수 $a/b$와 $c/d$ 사이에 새로운 기약분수 $(a+c)/(b+d)$를 추가한다.

생성되는 기약분수가 이렇게 간단한 산술 연산으로 표현된다는 사실은 자명하지 않다. 이에 대한 증명은 다음 사실로부터 따라온다. 임의의 Farey sequence에서 이웃한 두 기약분수 $a/b$와 $c/d$를 볼 때, 항상 $bc-ad=1$이라는 성질이 성립한다. 이는 간단한 귀납적 논의로 보일 수 있다.

이제 기약분수를 추가하는 과정에서 분모와 분자가 서로소가 아니라 가정해보자. 그러면 어떤 소수 $p$가 $a+c$와 $b+d$를 날 것이다. 간단한 mod 연산으로 $p$가 $bc-ad$를 나눠야 함을 알 수 있고, 이는 모순이다.

본 문제와 같이 분모가 $N$ 이하인 기약분수들만 구하고 싶다면, 추가하는 과정에서 $b+d\leq N$인 경우에만 추가를 해주면 된다. 이렇게 해도 위 성질들은 여전히 성립함을 알 수 있다.

이런 과정을 통해 문제에서 제시한 $A_N$을 구할 수 있게 된다. ICPC 2023 예선 G에서는 $N$의 값이 작아 수열을 직접 구하는 것이 가능했지만, 이 문제는 $N$이 매우 커 그렇게 할 수는 없다. 대신, 우리는 지금까지 보인 성질들을 이용해 어떤 분수의 바로 다음 항을 쉽게 계산할 수 있다.

$A_N$에서 기약분수 $a/b$의 다음 항을 계산해보자. 그 항을 $c/d$라 하면, 마찬가지로 $bc-ad=1$을 만족할 것이다. 또한 이 분수는 정의상 “분모가 $N$이하인 기약분수 중 $a/b$보다 큰 가장 작은 분수”이다. 즉, $c/d-a/b=(bc-ad)/bd=1/bd$가 최대한 작아야 한다. 따라서 이 두 사실로부터 우리는 다음과 같은 결론을 내릴 수 있다.

$a/b$의 다음 항 $c/d$는 $bc-ad=1$인 $(c,d)$ 중 $d$가 $N$ 이하의 최대값이 되도록 잡는 것이다.

위 과정은 확장 유클리드 호제법을 이용하면 $O(log N)$으로 계산 가능하다. 따라서 이 과정을 $j$번 반복하면 $O(j log N)$으로 이 문제를 해결할 수 있다.

그러나, 이 문제의 조건인 $j\leq 2\times10^7$과 $N\leq 10^{18}$에서는 위의 시간복잡도로 시간 제한을 통과하기 힘들다. 위 알고리즘을 보다 최적화해보자.

지금 시간이 오래 걸리는 이유는, 매번 다음 항을 계산할 때마다 유클리드 호제법을 사용하기 때문이다. 그런데 잘 생각해보면, 매번 유클리드 호제법이 필요하지는 않다. 이웃한 세 기약분수 $a_{n-1}/b_{n-1}$, $a_n/b_n$, $a_{n+1}/b_{n+1}$을 생각해보면, $a_n\times b_{n-1}-b_n \times a_{n-1}=1$과 $a_{n+1}\times b_n - b_{n+1}\times a_n=1$을 만족한다. 이때 첫번째 식을 잘 변형해보면 $(-a_{n-1})\times b_n - (-b_{n-1})\times a_n = 1$을 만족하는데, 이는 잘 보면 두 번째 식과 같은 꼴($x\times b_n - y\times a_n = 1$)이다. 즉 우리는 다음 항 $(a_{n+1}, b_{n+1})$을 찾기 위한 특수해 $(-a_{n-1}, -b_{n-1})$을 이미 알고 있는 것이며, 유클리드 호제법을 쓰는 대신 이 특수해를 사용하면 다음 기약분수를 계산할 수 있다.

따라서 첫 번째 항만 유클리드 호제법으로 직접 계산해주면, 그 다음부터는 이전 항을 이용해 다음 항을 계산할 수 있게 된다. 이때 시간복잡도는 $O(j + log N)$이다.

D. 위수는 쿼리입니까?

요약: 고정된 양의 정수 $N$에 대해 $\text{mod N}$에서 다음 네 쿼리를 계산하는 프로그램을 작성해야 한다.
(1) 어떤 수 $a$의 위수 구하기
(2) 어떤 수 $r$을 위수로 가지는 아무 수 구하기
(3) 어떤 수 $r$을 위수로 가지는 수의 개수
(4) 어떤 수 $r$을 위수로 가지는 수들의 합

우선 이 문제는 $N$이 고정되어 있기 때문에, N의 소인수분해 결과를 저장 및 전처리하여 이용할 수 있다. 기본적으로 위수에 대한 분석을 하려면 원시근의 존재성이 필요하다. 그러나 일반적인 합성수에서는 원시근의 존재성이 보장되지 않으므로, 소인수분해 결과 $N=p_1^{e_1}\cdots p_t^{e_t}$에서 각각의 mod $p_i^{e_i}$의 관점에서 생각해볼 것이다. (이때 $p_i=2$인 경우가 예외가 된다. 일반적으로 $3$ 이상의 $k$에 대해 $2^k$은 원시근을 안 가지기 때문에, 따로 처리해줘야 한다)

일반적으로 어떤 수 $X$의 소인수 개수(중복 포함)는 대략 $O(log X)$로 충분히 작다. 이 문제는 쿼리 개수 또한 작으므로, 소인수 개수 정도의 시간복잡도는 충분히 넉넉하다고 생각할 것이다.

일단 풀이를 완성하기 위해 다음 Lemma가 필요하다.(위수의 성질을 생각해보면 자명하다)

Lemma. $1\leq i\leq t$에 대해 $ord_{p_i^{e_i}}(a)=r_i$일 때, $r=ord_N(a)=LCM(r_1,\cdots,r_t)$이다.

1번 쿼리

편의상 $gcd(a, N)=1$이라 가정하겠다. Lemma에 의해 각각의 $r_i$를 계산하면 $r$을 계산할 수 있다. 이는 나이브하게 계산하면 된다. 가능한 최대 위수인 $\phi(p_i^{e_i})$에서부터 소인수를 하나씩 나눠보며 거듭제곱을 확인해보면 된다.

나머지 쿼리들

나머지 쿼리들을 해결하려면 기본적으로 위수가 $r$인 수들이 어떤 조건을 만족해야 하는지 알아야 한다. 우리는 Lemma에 따라 $LCM(r_1,\cdots,r_t)=r$인 모든 $r_i$ 쌍들에 대해, 각각의 mod $p_i^{e_i}$에서 위수가 $r_i$인 수들을 파악해야 한다.

$p_i=2$인 경우는 독자들에게 맡긴다. 힌트를 주자면, LTE Lemma를 이용하여 $a^x-1$의 $2$-지수를 정확히 계산할 수 있다. 이를 바탕으로 위수로 가능한 수가 무엇인지, 그리고 그때 가능한 $a$가 무엇인지를 구체적인 형태로 표현할 수 있다.

본 문제를 풀기 위해서는 다음 두 과정이 필요하다.
(1) 각각의 $p_i^{e_i}$에 대해 위수가 $r_i$인 수들의 성질 찾기
(2) 이 결과들을 합치기

나머지 쿼리들은 1번 과정을 공유하는 대신 2번 과정에서 큰 차이를 가진다.

1번 과정

편의상 $p_i=p, e_i=e, r_i=r$이라 쓰겠다. 우선 위수 $r$은 자명하게 $\phi(p^{e})$의 약수여야 한다. 또한 원시근 $g$를 잡을 수 있으므로, 각 약수 $r$ 별로 정확히 위수가 $r$인 실례 $a=g^{\phi(p^{e})/r}$가 존재한다.(2번 쿼리에 이 값을 사용하면 된다) 따라서 mod $p^e$에서 위수가 $r$인 수가 존재할 필요충분조건은 $r$가 $\phi(p^{e})$의 약수인 것이다. 이 조건을 충족시키지 않으면 $0$을 출력하면 된다.

위 조건을 만족한다 생각하고 문제를 풀어보자. 우선 가장 간단한 경우, $e=1$일 때를 생각해보자. 위수가 정확히 $r$인 수들은 원시근 $g$에 대해 $g^{k\times \phi(p^e)/r}(1\leq k\leq r, (k, r)=1)$로 표현된다. 따라서 개수는 정확히 $\phi(r)$개이다.(3번 쿼리의 답)

4번 쿼리, 즉 합을 구하는 것이 가장 어렵다. 단순히 closed form으로 표현하기는 어려운데, 이 과정에서 Mobius function을 이용할 것이다. 구체적으로, $\displaystyle\sum_{d\vert n}\mu(d)$가 $n=1$일 때만 $1$, 나머지는 $0$이라는 성질을 이용한다.

\[\sum_{1\leq k\leq r, (k, r)=1}g^{k\times \phi(p^e)/r}=\sum_{1\leq k\leq r}g^{k\times \phi(p^e)/r}\sum_{d|(k,r)}\mu(d)=\sum_{d|r}\mu(d)\sum_{d|k}g^{k\times \phi(p^e)/r}\equiv\mu(r)\text{ (mod p)}\]

식에 일반적인 지수 $e$를 도입하였는데, 마지막 합동식은 $e=1$일 때만 성립한다. 뫼비우스 함수를 도입한 후 합의 순서를 바꾸면, 뒤쪽 항은 단순한 등비수열의 합이 된다. 합을 계산해보면, 공비가 $1$이 아닌 이상 그 합이 $0$이 된다. 즉, $d=r$인 경우만 살아남게 된다.

거듭제곱의 지수가 올라가면 결과가 조금 더 복잡해진다. 구체적으로, 뒤쪽 항을 계산할 때 상쇄되지 않는 경우가 더 늘어난다. $d=r$이 아니더라도, $g^{k\times \phi(p^e)/r}-1$이 $p$의 배수인 경우는 전부 고려해줘야 한다. 구체적인 계산은 독자에게 맡긴다. 아래에 적힌 결과와 비교해보아라.

일반적인 결과는 다음과 같다: $r$의 $p$-지수가 $s$일 때, 답은 $f(r)\equiv\mu(r)+p\mu(r/p)+\cdots+p^s\mu(r/p^s)\text{ (mod }p^e\text{)}$이다.

2번 과정

각 쿼리에 대해 따로 다루겠다.

2번 쿼리

먼저 $LCM(r_1,\cdots,r_t)=r$이며 $r_i \vert \phi(p_i^{e_i})(1\leq i\leq t)$인 $r_i$들을 잡는다. 이는 $\phi(p_i^{e_i})$의 소인수분해 결과를 미리 저장하여 이용하면 쉽게 해결 가능하다. 각각의 $i$에 대해 위수가 $r_i$인 수를 mod $p_i^{e_i}$에서 잡았으므로, CRT로 실제 답을 계산하면 된다.

3번 쿼리

먼저 $r_i$ 쌍들을 고정한 상태로 생각해보자. CRT의 원리를 생각했을 때, 각각의 mod $p_i^{e_i}$에서 구한 개수들을 전부 곱하면 실제 mod $N$에서의 개수가 될 것이다. 따라서 이 곱들을 가능한 $r_i$ 쌍들에 대해 전부 더하면 된다. 이를 단순하게 계산하는 것은 힘들다. 그러나 다음 관찰을 하면 이를 쉽게 계산할 수 있다.

고정된 $p_i^{e_i}$에서 보았을 때, 위수가 $r_i$인 수의 개수는 정확히 $\phi(r_i)$으로 이는 곱산술함수이다. 따라서 우리가 $r_i$를 소인수분해한다면, 각각의 소수 거듭제곱에 대한 개수들의 곱으로 생각해도 무관하다. 이런 관점에서 보았을 때 최소공배수 조건 또한 쉽게 처리할 수 있다. 최소공배수 조건은 결국 각각의 소인수들에 대해 지수가 특정 부등호 조건을 만족해야 한다는 뜻이다. 즉, 최소공배수 조건 또한 소인수별로 따로 생각해도 무관하다.(여기서 다루는 소수 및 소인수는 $\phi(p_i^{e_i})$들의 소인수들이다)

각각의 가능한 $r_i$ 쌍들에 대한 개수의 곱을 위 내용과 같이 소수 거듭제곱 항들의 곱으로 분해하자. 각 소인수들은 독립적인 조건을 가지므로, 이 항들의 합은 잘 묶여서 “각 소인수들에 대한 답(개수의 곱의 합)”의 곱으로 표현될 것이다. “각 소인수 $p$에 대한 답”을 formal하게 표현하면 다음과 같다.

$\displaystyle\sum_{f_i\leq v_p(\phi(p_i^{e_i}))\text{ and }max(f_1,\cdots,f_t)=f}\phi(p^{f_1})\cdots\phi(p^{f_t})$

$=\displaystyle\sum_{f_i\leq v_p(\phi(p_i^{e_i}))\text{ and }f_1,\cdots,f_t\leq f}\phi(p^{f_1})\cdots\phi(p^{f_t})-\displaystyle\sum_{f_i\leq v_p(\phi(p_i^{e_i}))\text{ and }f_1,\cdots,f_t\leq f-1}\phi(p^{f_1})\cdots\phi(p^{f_t})$

우변의 각 항을 보면 $f_1,\cdots,f_t$끼리도 독립임을 알 수 있다. 따라서 이들 또한 잘 묶여서 각각의 $i$에 대한 답들의 곱으로 표현할 수 있다.

$=\displaystyle\prod_{i}\sum_{f_i\leq v_p(\phi(p_i^{e_i}))\text{ and }f_i\leq f}\phi(p^{f_i})-\displaystyle\prod_{i}\sum_{f_i\leq v_p(\phi(p_i^{e_i}))\text{ and }f_i\leq f-1}\phi(p^{f_i})$

$\sum$와 $\prod$ 안의 각 항은 정말 쉽게 계산할 수 있다! (그냥 closed form으로 표현 가능하다) 따라서 이 식을 계산할 수 있게 되었다.

4번 쿼리

3번 쿼리와 달리 CRT가 직접적으로 각 소수 거듭제곱에 대한 답들을 합쳐주지는 못한다. 따라서 다음과 같은 과정으로 답을 계산할 것이다.
(1) 최소공배수 조건을 만족하는 $r_i$들을 먼저 고정한다.
(2) 각각의 $1\leq i\leq t$에 대해 mod $p_i^{e_i}$ 위수가 $r_i$인 수들의 합을 mod $p_i^{e_i}$로 본 나머지를 구한다.
(3) CRT로 답을 구한다.

(2)는 다음과 같이 계산할 수 있다. 각각의 $i$에 대한 조건이 독립이므로, $\mathbb{Z}_{p_i^{e_i}}$에서 위수가 $r_i$인 수들의 합에다가 $i$를 제외한 나머지 mod들의 조합으로 가능한 경우의 수를 곱해주면 된다. 후자는 3번 쿼리와 거의 동일한 방법으로 계산 가능하다. 전자는 위에서 구했듯이 뫼비우스 함수들의 합으로 표현되는데, 여기서 재밌는 성질이 하나 있다.

고정된 $p$에 대해 위에서 구했던 함수 $f(r)$이 놀랍게도 곱산술함수이다. 핵심 원리는 서로소인 $a$와 $b$를 잡았을 때 둘 중 하나는 $p$의 배수가 아니라는 것이다. 이때 그 함수값은 단순한 뫼비우스 함수 값이 되고, 뫼비우스가 곱을 보존하므로 이 함수 또한 곱이 보존하게 된다.

따라서 3번 쿼리와 완전히 동일한 메커니즘을 사용할 수 있다. (당연히 식은 더 복잡하다) 각각의 $1\leq i\leq t$와 $\phi(p_i^{e_i})$의 소인수의 조합에 대해 $f$ 값을 계산해놓으면, 3번 쿼리와 비슷하게 이들의 합과 곱으로 답을 계산할 수 있다. 구체적인 과정은 마찬가지로 독자에게 맡긴다.

결론

내가 생각하는 이 문제의 핵심 아이디어는 뫼비우스 함수를 이용하여 합을 구하는 테크닉, 그리고 곱산술함수의 특성을 이용하여 식을 쉽게 계산하는 방법이다. 그리고 보다 싶이 구현이 많이 복잡하다.(필자의 정해는 8000B 정도 된다) 사실 이 문제의 시간복잡도는 많이 널널하다. 잘 생각해보면, 위에서 언급했던 계산 과정은 전부 전처리가 가능하다! 각 쿼리별로 필요한 정보만 가져오는 식으로 구현하면 시간 제한으로 문제를 겪진 않을 것이다.

사실 언급하지 않고 넘어간 중요한 내용이 있다. 바로 $2$의 거듭제곱에 대한 이야기이다. 원시근이 존재하지 않는 예외에 대해 따로 계산하였기 때문에, 이때 또한 위의 곱산술함수 테크닉을 사용할 수 있는지 확인이 필요하다. 결론적으로 아무 문제가 없는데, 왜냐하면 이때 가능한 위수들은 자명하게 $2$의 거듭제곱이기 때문이다. 이미 그 자체로 소수의 거듭제곱이므로, 소인수들 중 $2$를 다룰 때만 해당 경우를 잘 처리해주면 된다.