삼성SW아카데미/[Professional]1 5607. 조합 n^{p} \equiv n \left(\text{mod}\ p \right) N combination R의 값을 1234567891로 나눈 나머지를 출력. 즉, 우리에게 익숙한 nCr을 1234567891로 나눈 나머지를 출력하란 말이다. nCr을 구하는 공식을 보면 이다. 하지만 나머지 연산은 나눗셈에 적용할 수 없다. 그래서 이 식을 곱셈 형태로 바꿔줘야 하는데 여기서 사용되는 것이 페르마의 소정리이다. 페르마의 소정리에 의해서 P를 1234567891이라고 하면 가 성립한다. 제곱의 경우는 분할 정복을 통해서 O(logP)의 시간복잡도 안에 해결할 수 있기 때문에 해결이 가능하다. 123456789101112131415161718192021222324252627282930313233343536373.. 2020. 4. 4. 이전 1 다음