모듈러연산 코딩? 에 관해서 질문 드립니다.

Question

프로그래밍과 수학을 공부하는 학생입니다.

a의 b제곱 mod c를 계산 하는데, a와 c를 사용자가 입력하면 b의 값을 출력하는 코드를 알고싶습니다.

c언어나 파이썬 코드로 해주시면 감사하겠습니다.

Answer 1

BOJ 1629의 곱셈 문제같네요.

a의 b 제곱은 분할 정복으로 구현할 수 있습니다.

그리고 (a * b) mod c 는 (a mod c ) x (b mod c)와 같기 때문에,

매번 곱할 때마다 나머지 연산을 계속 해주면 overflow가 발생하지 않습니다.

설명이 잘 되어있는 블로그가 있어서 링크 달아드립니다.

https://bloodstrawberry.tistory.com/185