BOJ 16709 Congruence Equation

난이도 : Solved.ac 기준 다이아 3

출처 : 경기과학고 2018 송년대회 C번

 

1. 문제 설명

$10^{15}$ 정도의 큰 소수 $p$ 가 주어지고, $a^b \equiv b^a (\mod p)$ 를 만족하는 자연수 $1 \leq a, b \leq p(p-1)$ 순서쌍 $(a, b)$ 의 개수를 구하는 문제. 

 

 

 

2. 풀이

풀이의 수식 전개 과정이 상당히 복잡하고 요구하는 지식의 허들이 높은 대신, 코딩이 상대적으로 쉽다. 종이에 엄청 써 보고 나면 컴퓨터 잡고 나서는 금방 풀 수 있는 문제.

먼저, $a$ 와 $b$ 가 모두 $p$ 의 배수인 경우에는, $a^b$ 와 $b^a$ 가 모두 $\mod p$ 에 대해서 0이 되므로 주어진 조건을 만족한다. 이러한 경우는 주어진 범위 안에 $(p-1)^2$ 개 순서쌍이 존재하므로, 이들을 따로 생각하기로 하자.

이제 $a$ 와 $b$ 중 어느 한쪽이 $p$의 배수가 아닌 경우를 생각하자. 둘 중 한쪽이 $p$ 의 배수라면, 일반성을 잃지 않고 $b$가 $p$의 배수라고 할 때 $a^{kp} = {kp}^a$ 여야 한다. 이때, 우변은 자명하게 0이고, 좌변은 페르마의 소정리에 의해 $a^{kp} \equiv a^{k}$ 가 되는데, 이 값이 0일 수 없으므로 불가능하다. 즉, 두 수가 모두 $p$의 배수가 아닌 경우에만 가능하다는 것을 알 수 있다.

 

이제, 어떤 Primitive root $g$를 잡자. 존재성은 $p$ 가 소수이므로 항상 보장되고 (증명 링크) , 직접 찾을 필요는 없으므로 이를 찾는 시간은 고려하지 않아도 된다. $a = g^u$, $b = g^v$ 라고 하면 주어진 식은 $g^{ub} \equiv g^{va} \mod p$ 가 되고, 어차피 $a, b$ 가 $p$의 배수가 아님이 앞서 가정되었으므로 $p$로의 모듈러 대신 $p-1$ 의 모듈러를 취해도 된다. 즉, $ub = va \mod p-1$ 을 만족하는 $(a, b, u, v)$의 개수를 찾는 것으로 충분하다. 특히, $u, v$가 정해졌을 때 중국인의 나머지 정리에 의해 $ub = va \mod p-1$ 을 만족하는 $p(p-1)$ 이하의 자연수쌍 $a, b$ 가 유일하므로, 개수를 그대로 가져가도 된다는 사실을 알 수 있다. 

 

어떤 $a$에 대해, 즉 원시근을 이용한 표현으로는 $(a, u)$ 가 어떤 값으로 정해져 있을 때 가능한 $(b, v)$의 순서쌍의 개수를 셀 수 있다고 하면, 다음 식으로 답을 표현할 수 있다. $a = 0$ 같은 경우 식 전개 과정에서 $\gcd$ 등을 쓰기가 애매하므로, 0부터 $p-2$ 까지 대신 1부터 $p-1$ 까지로 생각하자.

$$\sum_{a = 1}^{p-1} \sum_{u = 1}^{p-1} f (a, u)$$

 

$f(a, u)$에 대해 열심히 수식을 전개해 보면, 다음과 같은 결과를 얻을 수 있다. 자세한 증명은 수식이 상당히 복잡하기도 하고, 이 문제를 출제하신 분의 설명이 매우 자세하게 잘 되어 있어서 (링크) 생략한다. 앞서 $g$를 잡아서 표현을 고치는 아이디어도 잘 설명되어 있으므로, 다시 다루지 않는다. 아래의 수식 전개도 똑같고, 출제 의도는 아마 Dirichlet Convolution 같은걸로 계산을 빠르게 하는 것 같다. 

 

$$\sum_{a = 1}^{p-1} \sum_{u = 1}^{p-1} (p-1)\gcd(a, u, p-1)$$

$p-1$ 은 내부 계산과 무관하므로 앞으로 뺄 수 있고, 다음 식을 빠르게 계산할 수 있으면 된다.

$$\sum_{a = 1}^{p-1} \sum_{u = 1}^{p-1} \gcd(a, u, p-1)$$

 

잘 알려진 명제로, $gcd(u, p-1) = d$ 인 $u$ 의 개수는 정확히 $\phi(\frac{p-1}{d})$ 개이다. 따라서, 주어진 식을 

$$\sum_{d | p-1} \phi\left(\frac{p-1}{d}\right) \sum_{a = 1}^{p-1} \gcd(a, d)$$

안쪽의 시그마를 같은 방법으로 풀어서, $$\sum_{d | p-1} \phi\left(\frac{p-1}{d}\right) \sum_{e | d} \frac{e(p-1)}{d}\phi\left(\frac{d}{e}\right)$$

 

$\frac{e(p-1)}{d}$의 값을 고정 ($k$) 하는 방법으로 식을 잘 전개해서,

$$\sum_{k|(p-1)} k^2 \phi \left( \frac{p-1}{k} \right)$$ 까지 식을 정리할 수 있고, 최종 답은

$$(p-1)^2 + (p-1)\sum_{k|(p-1)} k^2 \phi \left( \frac{p-1}{k} \right)$$

이 식은 단순히 모든 $p-1$ 의 약수에 대해 오일러 파이 함수를 계산해도 된다. 

 

 

2-2. 시간 복잡도?

수식 계산은 모두 종이에 손으로 하는 것이고, 실제로 컴퓨터가 계산하는 식은 

$$(p-1)^2 + (p-1)\sum_{k|(p-1)} k^2 \phi \left( \frac{p-1}{k} \right)$$

이 식 뿐이다. 이 식을 정말로 naive하게 계산해도 될지는 믿음을 가지고 코딩해도 되지만, 약간 Bound를 잡아서 생각해 볼 수는 있을 것 같다.

오일러 파이 함수의 값 $\phi(n)$이 얼마인지 Evaluate 하기 위해서는 $O(\sqrt{n})$ 시간에 할 수 있다. 수식에서 알 수 있듯이 모든 약수에 대해 오일러 파이 함수를 계산해야 하므로 전체 코드의 수행 시간은 대략적으로 

$$\sum_{d | (p-1)} \sqrt{d}$$ 정도 시간임을 알 수 있다. 약수의 제곱근의 합이 얼마 정도 되는지가 결국 유의미하다고 할 수 있겠다. 

 

먼저, 임의의 음이 아닌 실수 $x_1, x_2, \dots x_n$ 에 대하여, 

$$\sqrt{ \frac{x_1^2 + x_2^2 + \dots x_n^2}{n}} \geq \frac{x_1 + x_2 + \dots x_n}{n}$$ 임이 잘 알려져 있다. (RMS-AM Inequality)

 

이제, 위 수식에서 $d_1 \dots d_m$ 을 각각의 약수라고 생각하고, $m$을 $p-1$의 약수의 개수라고 하자. 이때, $d_i$ 대신 $\sqrt{d_i}$ 를 쓰면, 

$$\sqrt{\frac{d_1 + d_2 + \dots d_m}{m}} \geq \frac{\sqrt{d_1} + \sqrt{d_2} \dots +\sqrt{d_m}}{m}$$

 

즉, 우리가 원하는 값을 $K$ 라고 하면, 

$$K \leq \sqrt{\text{number of divisors}} \times \sqrt{\text{sum of divisors}}$$

 

구글링을 좀 해보면 두 함수 모두 매우 유명하기 때문에 많은 Bound가 알려져 있다. 대표적으로, 약수들의 합이 $O(n \log \log n)$ 정도의 Growth rate 를 가지며, 약수들의 개수는 임의의 $\epsilon$에 대해 $o(n^\epsilon)$ 하다는 사실도 알 수 있다. 특히 다음과 같은 바운드가 알려져 있다.

$$\limsup \frac{\log d(n) \log \log n}{\log n} = \log 2$$

 

어쨌든 결과적으로, 대충 $O(\sqrt{n})$ 보다 조금 더 큰 (로그가 잔뜩 붙는 이상한 함수만큼 더 큰) Asymptotic Growth를 갖는다는 확신을 가질 수 있고, $\sqrt{n}$ 이 $10^{7.5}$ 이므로 이정도면 믿음을 가지고 짜서 넣을만 하다. ㅎㅎ!

 

 

3. 코드

앞서 작성한 수식이 충분히 Self-Explanatory 하고 구현상의 별다른 특이점이 없다.