페르마의 소정리

백준 11401 풀이 (이항 계수 3, 페르마의 소정리, 정수론, 분할알고리즘)

이번 문제는 너무나 어려웠다. 처음에는 어떻게든 풀어보려고 이항계수 강의도 듣고, 페르마의 소정리도 찾아보며 어떻게 풀어야할지 고민하기 시작했다. 물론 이게 하루이틀이지 계속 생각해도 안풀려서 고수의 도움을 받았다ㅋㅋㅋㅋ 여튼 내가 이해한 것을 천천히 정리해보자. 문제를 보면 1초의 시간제한이 존재한다. 또한 N값이 4,000,000으로 상당히 큰 수이다. 마지막으로는 1,000,000,007로 나눈 값을 출력하면 된다. 우선 이항계수를 공부하며 몇가지 규칙을 알게 되었다. 이항 계수를 한방에 이해할 수 있는 파스칼의 삼각형이다. 여기를 보면 규칙을 찾을수 있다. 규칙은 nCk = n-1Ck-1 + n-1Ck 이며 이것을 구하는 식을 나타내면 아래와 같다. 그러나 문제는 이러한 방식으로 엄청나게 큰 수를..