BOJ 16709 Congruence Equation
알고리즘 문제풀이/BOJ
2020. 2. 1. 00:24
난이도 : 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..
