궤도

문제 풀이 페르마의 소정리를 이용해 곱셈의 역원을 구하라던 힌트를 보고 당황했다. 일단 페르마의 소정리가 뭔지 모르겠고, 이항 계수문제랑 곱셈의 역원이 무슨 상관인지도 몰랐기 때문이다. 그래서 힌트를 좀 봤다. 이항계수를 정리하면 대충 이런 모습인데 우리는 이걸 1,000,000,007로 나눈 나머지를 구해야 한다. 그렇다고 이럴 순 없다. 왜냐하면 나머지는 0이 나올 수도 있고, 분모가 0이 되면 안되기 때문이다. 그래서 B의 역원을 구한 뒤 그 값에 대해 나머지 연산을 해야한다. 그리고 그 역원 계산에 페르마의 소정리가 필요한 것이다. ko.wikipedia.org/wiki/%ED%8E%98%EB%A5%B4%EB%A7%88%EC%9D%98_%EC%86%8C%EC%A0%95%EB%A6%AC 페르마의 소..