Algorithm_with_Python/1629.py at master · barryahn/Algorithm_with_Python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# 1629 곱셈

a, b, n = list(map(int, input().split()))
result = 1

def divide(a, b):
    global result
    global n
    if b == 1:
        return a % n
    else:
        temp = divide(a, b // 2)
        if b % 2 == 0:
            return temp * temp % n
        else:
            return temp * temp * a % n

print(divide(a, b))

"""
a, b, n = list(map(int, input().split()))
result = 1

def divide(a, b):
    global result
    global n
    if b == 1:
        result *= a % n
    else:
        if b % 2 == 0:
            divide(a, b // 2) * divide(a, b // 2) % n
        else:
            divide(a, b // 2) * divide(a, (b + 1) // 2) % n
    result *= a % n

divide(a, b)
print(result % n)
"""