hwpark12   2년 전

항상 궁금했던 건데 오늘 드디어 글을 써봅니다...

답을 출력할 때 100000007과 같은 소수로 나눈 나머지를 출력하라는 문제들이 있는데요

답을 다 구해놓고 출력 직전에 나머지 연산을 하기에는 값이 너무 커지는 경우가 많이 있었습니다.

답을 계산하는 과정에서 중간중간 나머지 연산을 통해 값을 줄여줘야 하는 문제들이 있는데

계산 과정 도중 덧셈이나 곱셈 이외에 나눗셈이 들어갔을 때 정답이 달라지는 것은 어떻게 처리해야 하나요?

예를 들면 mod 7일 때

64*32 는 1*4와 합동이지만 64//32는 1//32로 값이 달라지는 경우입니다.

도와주세요 ㅠㅠ

p_ce1052   2년 전

어떤 문제를 푸시는지 모르겠지만 페르마의 소정리를 공부하시면 도움이 될 것 같네요 

hwpark12   2년 전

답변 감사드립니다! 페르마 소정리와 모듈러 곱셈 역원을 공부하니 해결되었습니다.

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