문제 출처: https://www.acmicpc.net/problem/11401 1. 결과 메모리 188804KB, 시간 1144ms 2. 풀이 이 문제를 처음에 풀이할 때는 혼란스러웠다. 분할 정복과 재귀 호출 등을 사용해서 팩토리얼 연산 횟수를 최대한 줄이는 것이 문제의 요점이라고 생각했다. 하지만 그렇게 풀이한 코드는 채점 결과 런타임 에러를 발생했고, 생각해보면 최대 400만 번의 재귀 호출이 발생할 수 있기 때문에 납득할 수 있는 결과였다. 하지만 그렇다면?? 어떤 풀이로 접근을 해야 할지 고민을 하며 다른 블로그와 풀이 아이디어만을 참고하려고 검색하던 중 '페르마의 소정리'를 이용하는 문제라는 것을 알았다. 페르마의 소정리란 코드의 주석 부분에 작성한 것처럼 소수인 p와 그 p의 배수가 아닌 ..
