-
[Python] ๋ฐฑ์ค - 1629 ๊ณฑ์ __Python/__Algorithm 2022. 1. 13. 17:01
๋ฌธ์
https://www.acmicpc.net/problem/1629
๐น ๋ฌธ์
์์ฐ์ A๋ฅผ B๋ฒ ๊ณฑํ ์๋ฅผ ์๊ณ ์ถ๋ค. ๋จ ๊ตฌํ๋ ค๋ ์๊ฐ ๋งค์ฐ ์ปค์ง ์ ์์ผ๋ฏ๋ก ์ด๋ฅผ C๋ก ๋๋ ๋๋จธ์ง๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
๐น ์ ๋ ฅ
์ฒซ์งธ ์ค์ A, B, C๊ฐ ๋น ์นธ์ ์ฌ์ด์ ๋๊ณ ์์๋๋ก ์ฃผ์ด์ง๋ค. A, B, C๋ ๋ชจ๋ 2,147,483,647 ์ดํ์ ์์ฐ์์ด๋ค.
๐น ์ถ๋ ฅ
์ฒซ์งธ ์ค์ A๋ฅผ B๋ฒ ๊ณฑํ ์๋ฅผ C๋ก ๋๋ ๋๋จธ์ง๋ฅผ ์ถ๋ ฅํ๋ค.
ํ์ด ๋ฐฉ๋ฒ
๐น ์ฌ๊ท
๐นA5 = (A2)2*A
๐น Pow ํจ์ ๋ด while๋ฌธ์ผ๋ก ๊ตฌํํ์ผ๋ ์๊ฐ์ด๊ณผ(ํ ์คํธ์ผ์ด์ค ์คํ ํ์ ๋์ผ, ์ฐ์ฐ๊ฐ์ ํจ์ฌ ํผ)์ผ๋ก ์ฌ๊ท๋ก ๋ณ๊ฒฝ.
๊ตฌํ ์ฝ๋
import sys a,b,c = map(int, sys.stdin.readline().split()) def Pow(b): if b==0: return 1 r = b%2 tmp = (Pow(b//2)**2)%c if r == 0: return tmp return a*tmp % c print(Pow(b))
์คํ ๊ฒฐ๊ณผ
๐ก
๐น ๋ถํ ์ ๋ณต
๋ถํ ์ ๋ณต๋ฒ์ ์ฌ๊ท์ ์ผ๋ก ์์ ์ ํธ์ถํ๋ฉด์ ๊ทธ ์ฐ์ฐ์ ๋จ์๋ฅผ ์กฐ๊ธ์ฉ ์ค์ด๊ฐ๋ ๋ฐฉ์์ด๋ค. ( ์ถ์ฒ: ๋๋ฌด์ํค )
728x90'__Python > __Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Python] ๋ฐฑ์ค - 7569 ํ ๋งํ (0) 2022.02.12 [Python] ๋ฐฑ์ค - 1439 ๋ค์ง๊ธฐ (0) 2022.01.27 [Python] ๋ฐฑ์ค - 1463 1๋ก๋ง๋ค๊ธฐ (0) 2022.01.07 [Python] ๋ฐฑ์ค - 2805 ๋๋ฌด ์๋ฅด๊ธฐ (0) 2022.01.07 [Python] ๋ฐฑ์ค - 11399 ATM (0) 2022.01.07