[PY] 1629 : 곱셈

https://www.acmicpc.net/problem/1629

풀어봤음에도 문제가 참 신경쓰인다.

이 문제의 생각 방향을 서서히 설명하면 :

  1. a를 b번 곱하고 마지막에 c로 나눠 나머지를 얻어본다 :
    1. 범위 초과가 나니 못한다.
  2. 모듈러 연산의 법칙을 이용한다. 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