BOJ / 1629번 / 곱셈 [Go][Python3]

👩🏻‍💻 문제

1629번: 곱셈

---

✍🏻 풀이

🎨 Go

// https://www.acmicpc.net/problem/1629
// 분할 정복으로 거듭제곱을 빠르게 계산하는 문제
package main

import (
	"bufio"
	"fmt"
	"math/big"
	"os"
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var a, b, c int64
	fmt.Fscanln(reader, &a, &b, &c)
	fmt.Fprintln(writer, getPower(a, b, c))
}

func getPower(a, b, c int64) (result int64) {
	if b == 0 {
		result = 1
		return
	}
	if b == 1 {
		result = a % c
		return
	}
	recur := getPower(a, b/2, c) % c
	temp := new(big.Int)
	m := new(big.Int)
	temp = temp.Mul(big.NewInt(recur), big.NewInt(recur))
	m = temp.Mod(temp, big.NewInt(c))
	if b%2 == 0 {
		result = m.Int64()
		return
	}
	result = m.Int64() * a % c
	return
}

🎨 Python3

# https://www.acmicpc.net/problem/1629
# 분할 정복으로 거듭제곱을 빠르게 계산하는 문제
import sys

sys.setrecursionlimit(10000)

def get_power(a, b, c):
    if b == 0:
        return 1
    elif b == 1:
        return a%c
    recur = get_power(a, b//2, c) % c
    if b % 2 == 0:
        return (recur % c) * (recur % c) % c
    return (recur % c) * (recur % c) * a % c

if __name__ == "__main__":
    a, b, c = list(map(int, sys.stdin.readline().split()))
    print(get_power(a, b, c))