dolmul5000   3일 전

짝수에 대한 경우와 홀수에 대한 처리가 조금 다른 것은 인식했습니다.

a^11 = (a^5)^2 * a

a^10 = (a^5)^2

그런데 중간중간 % c 를 하여도 답에는 아무 이상이 없나요 ? 

간단한 예시를 들어서 설명해주시면 감사하겠습니다.

djm03178   3일 전

덧셈과 곱셈으로만 이루어진 식에서는 언제 어디서든 mod를 해도 됩니다.

쉬운 예시로, 10진법의 수로 덧셈과 곱셈으로만 이루어진 식에서 1의 자리를 구해야 하는 경우를 생각해 보면 나머지는 무시하고 항상 1의 자리만 보더라도 된다는 것을 알 수 있습니다. 마찬가지로 c진법의 수에서 덧셈과 곱셈으로만 이루어진 식이 있다면 c로 나눈 나머지, 즉 c진법에서 마지막 자리의 수만 추적하더라도 결과는 같습니다.

댓글을 작성하려면 로그인해야 합니다.