https://www.acmicpc.net/problem/1629
풀어봤음에도 문제가 참 신경쓰인다.
이 문제의 생각 방향을 서서히 설명하면 :
- a를 b번 곱하고 마지막에 c로 나눠 나머지를 얻어본다 :
- 범위 초과가 나니 못한다.
- 모듈러 연산의 법칙을 이용한다. a * b에 mod c를 한 것은 a, b에 각각 mod c를 하고 또 그 결과에다가도 mod c를 하는것과 같다.
def func(originNum, multiPleNum, modNum, total):
if multiPleNum <= 1:
print(str(total))
return
originNum = originNum % modNum
originNum = originNum ** 2
total += originNum % modNum
total %= modNum
multiPleNum -= 1
func(originNum, multiPleNum, modNum, total)
func(inputA, inputB, inputC, 0)
안된다. 시간 초과가 난다.
3. 모듈러 연산을 이용하되 호출하는 횟수를 줄인다.
import sys
inputA, inputB, inputC = list(map(int, sys.stdin.readline().strip().split()))[:3]
sys.setrecursionlimit(10**8)
# 모듈러 연산의 분배 가능한 점을 이용하기
# a * b 를 mod m 하는 것은
# a mod m * b mod m * mod m 과 같다.
# 근데 여기선 inputA를 inputB 번 곱한 것을 inputC로 나눠서 출력하라고 하네.
# 그럼 a = b 이다.
def func(originNum, multiPleNum, modNum):
if(multiPleNum <= 1):
return originNum % modNum
value = func(originNum, multiPleNum // 2, modNum)
if multiPleNum % 2 == 0:
return (value * value) % modNum
else:
originToMod = originNum % modNum
return (value * value * originToMod) % modNum
print(func(inputA, inputB, inputC))
1. 우선 /2 승의 값을 구해와다가 홀수인경우 섭섭치 않게 한번 더 곱하는 식으로 해결 했다.
끝!
'문제풀이' 카테고리의 다른 글
[PY] 2110 : 공유기 설치 (0) | 2025.03.24 |
---|---|
[PY] 11503 : 가장 긴 증가하는 부분 수열 (0) | 2025.03.23 |
[PY] : 2630 색종이 만들기 (0) | 2025.03.22 |
[PY] 2805 : 나무 자르기 (0) | 2025.03.21 |
[PY] 1920 : 수 찾기 (0) | 2025.03.21 |