백준 1629(곱셈) - python
2023. 9. 29. 20:17ㆍ알고리즘(python)/그 외
접근
큰수의 제곱문제. 연산 횟수를 줄이는 문제인데 12^4 을 (12^2)^2 이런식으로 연산 횟수를 줄일 생각을 했다.
또 중요한 부분이 수를 줄이는 것인데 A**B의 결과에 C를 나누는 것이나. A%C **B나 결과가 같게 나온다는 것을
이용해야겠다는 생각을 했다.
예시
12*12 = 144
144%7 = 4
(12%7) * (12%7) = 25
25 % 7 = 4
나의 코드
import sys
input = sys.stdin.readline
A,B,C = map(int,input().split())
count = 1
cnt = 0
while B >= 5:
if B%2 == 1:
count *= A
A = (A**2) %C
B = B//2
print(((A**B)*count)%C)
'알고리즘(python) > 그 외' 카테고리의 다른 글
데이터분석 수학기초론 4장 문제풀이 (0) | 2023.10.11 |
---|---|
백준 1991(트리 순회) - python (1) | 2023.10.05 |