๐๋ฌธ์ ๋ณด๋ฌ๊ฐ๊ธฐ
๐ง๐ป๐ปํ์ด ๊ณผ์
์ฒ์ ๋ฌธ์ ๋ฅผ ๋ดค์ ๋๋ ๋ฌธ์ ๊ฐ ์ํ๋ ๊ฒ ๋ญ๊ธธ๋ ์ค๋ฒ 1์ผ๊น ์๊ฐํ๋๋ฐ, ์ฃผ์ด์ง ์ซ์ ๋ฒ์๊ฐ ๋ชจ๋ ์ต๋ 2,147,483,647์ด๋๊ตฐ์... ์ฆ, \(O(n)\) ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ์์ฑํ๊ฒ ๋๋ฉด ์ต๋ 2,147,483,647(21์ต) ๋ฒ ๋๊ธฐ ๋๋ฌธ์, ์๊ฐ ๋ด๋ก ์ ๋ ๋ชป ํต๊ณผํฉ๋๋ค.
\( O(logN) \) ์ ๋๋ ๋์ด์ผ ํ ์ ์์ํ ๋ฐ, ์ด๋ป๊ฒ ํ ๊น ํ๋ค๊ฐ ์ ๋ 2๊ฐ์ฉ ๋ฌถ๋ ๋ฐฉ๋ฒ์ ์ ํํ์์ต๋๋ค.
2๊ฐ์ฉ ๋ฌถ๊ฒ ๋๋ฉด, ๋ค์ ๋ ๊ฐ์ง ์ํฉ์ ์ง๋ฉดํ๊ฒ ๋ฉ๋๋ค.
- B๊ฐ ์ง์์ผ ๊ฒฝ์ฐ \( \rightarrow \) ๋จ๋ ๊ฒ ์์ด ๋ชจ๋ ๋ฌถ์ด๋ฏ๋ก ๊ทธ๋๋ก ์งํ
- B๊ฐ ํ์์ผ ๊ฒฝ์ฐ \( \rightarrow \) 1๊ฐ๊ฐ ๋จ์ผ๋ฏ๋ก, ๋ณ๋๋ก ๊ณฑํด์ฃผ๊ธฐ
๊ฐ๋ น 6์ 11๋ฒ ๊ฑฐ๋ญ์ ๊ณฑํด์ผ ํ๋ ์ํฉ์ ์์๋ก ๋ค์ด๋ณด๊ฒ ์ต๋๋ค.
6 6 6 6 6 6 6 6 6 6 6
6์ ๋ ๊ฐ์ฉ ๋ฌถ์ผ๋ฉด ์ด 5๊ฐ๋ก, 6์ด ํ๋๊ฐ ๋จ๋ ์ํฉ์ด ๋ฉ๋๋ค.
(6 6) (6 6) (6 6) (6 6) (6 6) 6
์ฆ, \( 6 \times 6 = 36 \)์ด 5๊ฐ๊ฐ ์๊ธฐ๊ฒ ๋ฉ๋๋ค. ํ๋ ๋จ์ 6์ ๋ณ๋๋ก ๊ณฑํด์ฃผ๊ธฐ๋ก ํ๊ณ , 36์ ๋ค์ ๋ ๊ฐ์ฉ ๋ฌถ์ต๋๋ค.
๊ทธ๋ฌ๋ฉด \( 36 \times 36 = 1296 \)์ด 2๊ฐ๊ฐ ์๊ธฐ๊ฒ ๋๊ณ , 36์ด ํ๋ ๋จ๊ฒ ๋ฉ๋๋ค.
(1296) (1296) 36
๋ง์ฐฌ๊ฐ์ง๋ก 36๋ ๋์ค์ ๋ณ๋๋ก ๊ณฑํด์ฃผ๊ธฐ๋ก ํ๊ณ , ๋ค์ 2๊ฐ์ฉ ๋ฌถ์ด๋ณด๊ฒ ์ต๋๋ค.
2๊ฐ ๋จ์์ผ๋ฏ๋ก 1๊ฐ๋ฐ์ ์์ฑ๋์ง ์์ต๋๋ค.
1679616
์ด ์ซ์์ ์๊น ๋ณ๋๋ก ๋จ์๋ 6, 36์ ๊ณฑํด์ฃผ๋ฉด ๊ฑฐ๋ญ์ ๊ณฑ ์ต์ข ๊ฒฐ๊ณผ๊ฐ ๋์ค๊ฒ ๋ฉ๋๋ค.
1679616 * 6 * 36
๋ฌผ๋ก ์ค๋ฒํ๋ก์ฐ๊ฐ ๋์ง ์๋๋ก, ์ค๊ฐ ์ฐ์ฐ ๊ณผ์ ๋ง๋ค % C๋ฅผ ํด์ฃผ๋ ๊ฒ์ ์์ง ๋ง์์ผ ํฉ๋๋ค.
์ด๋ฌํ ๊ณผ์ ์ ๋ฐ๋ณตํ์ฌ ๋ต์ ๊ตฌํ ์ ์์ต๋๋ค.
โ๏ธ์์ค ์ฝ๋ ๋ฐ ๊ฒฐ๊ณผ
#include <iostream>
#include <vector>
#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
using namespace std;
using uint64 = unsigned long long;
uint64 Pow(uint64 A, int B, const int C)
{
if (B <= 1)
return A % C; // (A:4, B:1, C:2)์ ๊ฐ์ ์
๋ ฅ๋ ์กด์ฌํ๋ฏ๋ก
int numCount = B / 2;
int mod = B % 2;
uint64 square = (A * A) % C;
uint64 modNum = (mod == 0) ? 1 : A;
return (modNum * Pow(square, numCount, C)) % C;
}
int main()
{
FAST_IO
int A, B, C;
cin >> A >> B >> C;
uint64 answer = Pow(A, B, C);
cout << answer;
return 0;
}
'๐คAlgorithm > BOJ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ] 13335๋ฒ | ํธ๋ญ (C++) (0) | 2023.09.04 |
---|---|
[BOJ] 1654๋ฒ | ๋์ ์๋ฅด๊ธฐ (C++) (0) | 2023.09.02 |
[BOJ] 1780๋ฒ | ์ข ์ด์ ๊ฐ์ (C++) (0) | 2023.08.31 |
[BOJ] 1992๋ฒ | ์ฟผ๋ํธ๋ฆฌ (C++) (0) | 2023.08.31 |
[BOJ] 2630๋ฒ | ์์ข ์ด ๋ง๋ค๊ธฐ (C++) (0) | 2023.08.31 |