[알고리즘/분할정복] 1629번 : - python

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

1629번: 곱셈

 

---

• 문제
• 소요시간: 11분 실패

---

• 설계하기(접근방법) 

1. 입력받기

a,b,c 를 입력받는다

 

2. 구현하기

이 문제는 

지수의 법칙과 나머지 분배법칙을 알고 있어야 한다

 

즉 

(10 ^ 12) % c를 계산한다고 했을 때

(10 ^ 6 * 10 ^ 6) % c 를 할 수 있다

그리고 나머지 분배 법칙은

((10 ^ 6 % c) * (10 ^ 6 % c )) % c를 할 수 있다

또한

(10 ^ 3 * 10 ^ 3 * 10 ^ 3 * 10 ^ 3 *) % c 와 같기 때문에

분할 정복해주면 답을 빠르게 얻을 수 있다

 

3. 출력하기

답을 출력한다

 

 

---

• 코드(출력)

n, m , c = map(int,input().split())

def power(a,b):
    if b == 1:
        return a % c
    else:
        tmp = power(a,b//2)
    if b % 2 == 0:
        return (tmp * tmp) % c
    else:
        return (tmp * tmp * a) % c
print(power(n,m))

---

• 얻어갈 부분

1. 아이디어가 떠오르질 않아서 빨리 포기하길 잘 한것 같다.