BOJ 16709 Congruence Equation
알고리즘 문제풀이/BOJ
2020. 2. 1. 00:24
난이도 : Solved.ac 기준 다이아 3 출처 : 경기과학고 2018 송년대회 C번 1. 문제 설명 1015 정도의 큰 소수 p 가 주어지고, ab≡ba(modp) 를 만족하는 자연수 1≤a,b≤p(p−1) 순서쌍 (a,b) 의 개수를 구하는 문제. 2. 풀이 풀이의 수식 전개 과정이 상당히 복잡하고 요구하는 지식의 허들이 높은 대신, 코딩이 상대적으로 쉽다. 종이에 엄청 써 보고 나면 컴퓨터 잡고 나서는 금방 풀 수 있는 문제. 먼저, a 와 b 가 모두 p 의 배수인 경우에는, ab 와 ba 가 모두 modp 에 대해서 0이 되므로 주어진 조건을 만족한다. 이러한 경우는 주어진 범위 안에 $(p-1)^2..
