๋ฌธ์
https://www.acmicpc.net/problem/1629
๋ฐฑ์ค ๋จ๊ณ๋ณ ํ์ด - ๋ถํ ์ ๋ณต
ํ์ด
์์ฐ์ A๋ฅผ B๋ฒ ๊ณฑํ ๊ฐ์ ๊ตฌํ๋ ๋ฌธ์ ๋ค. ๋จ, ๊ฐ์ด ๋งค์ฐ ์ปค์ง ์ ์์ผ๋ฏ๋ก C๋ก ๋๋์ด์ผ ํ๋ค.
์ ํ์๊ฐ์ 0.5์ด์ธ๋ฐ... ์ด๊ฑธ ์ด๋ป๊ฒ ๋ถํ ํ๋๋?
๋ง์ฝ A, B๊ฐ 2, 8๋ก ์ฃผ์ด์ก๋ค๊ณ ๊ฐ์ ํด๋ณด์.
8์ ์ง์์ด๋ฏ๋ก ๋จ์ํ ๋ฐ์ผ๋ก ์ชผ๊ฐ์ฃผ๋ฉด ๋๋ค.
$ 2^8 $
$ = 2^4 * 2^4 $
$ = 2^2*2^2 * 2^2*2^2 $
๊ฐ ๋ ๊ฒ์ด๋ค.
ํ์๋ผ๋ฉด?
$ 2^5 $
$ = 2 * 2^4 $
$ = 2 * 2^2*2^2 $
๊ฐ ๋๊ฒ ๋ค.
์ฆ, ์ง์์ผ๋ B//2๋ฅผ, ํ์์ผ๋ A * B//2๋ฅผ ๊ณฑํด์ฃผ๋ฉด ๋๋ค.
B๊ฐ 0์ผ๋ก ์ฃผ์ด์ง๋ or B๊ฐ 1์ผ๋ B//2๋ ์์ฐ์^0 = 1 ์ด๋ฏ๋ก 1์ ๋ฐํํด์ฃผ๋๋ก ํ๋ค.
# ๋ฉ๋ชจ๋ฆฌ: 31120KB / ์๊ฐ: 32ms
A, B, C = map(int, input().split())
def square(a, b, c):
if b == 0:
return 1
half = square(a, b//2, c)
if b % 2 == 0:
return (half * half) % c
else:
return (half * half * a) % c
print(square(A, B, C))
๋จผ์ ๊ณฑ์
์ ์ฒ๋ฆฌํ ํจ์ square()์ ๋ง๋ค์ด์ค๋ค.
b๋ฅผ ๋ฐ์ผ๋ก ์ชผ๊ฐ ๊ฐ์ half๋ก ํ ๋นํ ๋ค,
b๊ฐ ์ง์๋ผ๋ฉด ๊ทธ๋๋ก half * half๋ฅผ,
ํ์๋ผ๋ฉด a * half * half๋ฅผ ๋ฐํํ๋ค. (๋ฌผ๋ก c๋ก ๋๋จธ์ง๊ฐ ์ฒ๋ฆฌ๋ฅผ ํด์ค์ผ ํ๋ค.)
A, B = 2, 4 ๋ฅผ ์์๋ก ๋ค์ด๋ณด์ ๐
square(2, 4, c)(b = 4 ์ง์์ด๋ฏ๋ก ๊ทธ๋๋ก b//2)
=square(2, 2, c) * square(2, 2, c)=square(2, 1, c) * square(2, 1, c) * square(2, 1, c) * square(2, 1, c)์ด์ b๋ 1์ธ ์ํ๋ค.
์ฌ๊ธฐ์b//2 = 0์ด๋ฏ๋ก half๋ 1, ๊ทธ๋ฆฌ๊ณ b๊ฐ ํ์์ด๋ฏ๋กelse๋ฌธ์ผ๋ก ๋์ด๊ฐ์ 1 * 1 * 2 ๋ฅผ ๋ฐํํ๊ฒ ๋๋ค.
์ฆsquare(2, 1, c) = 2๊ฐ ๋๋๊ฒ์ด๋ค.