생활
모듈러연산 코딩? 에 관해서 질문 드립니다.
프로그래밍과 수학을 공부하는 학생입니다.
a의 b제곱 mod c를 계산 하는데, a와 c를 사용자가 입력하면 b의 값을 출력하는 코드를 알고싶습니다.
c언어나 파이썬 코드로 해주시면 감사하겠습니다.
1개의 답변이 있어요!
BOJ 1629의 곱셈 문제같네요.
a의 b 제곱은 분할 정복으로 구현할 수 있습니다.
그리고 (a * b) mod c 는 (a mod c ) x (b mod c)와 같기 때문에,
매번 곱할 때마다 나머지 연산을 계속 해주면 overflow가 발생하지 않습니다.
설명이 잘 되어있는 블로그가 있어서 링크 달아드립니다.