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