2023. 9. 1. 14:30ใCoding Test/BOJ
๐๋ฌธ์ ๋ณด๋ฌ๊ฐ๊ธฐ
1629๋ฒ: ๊ณฑ์
์ฒซ์งธ ์ค์ A, B, C๊ฐ ๋น ์นธ์ ์ฌ์ด์ ๋๊ณ ์์๋๋ก ์ฃผ์ด์ง๋ค. A, B, C๋ ๋ชจ๋ 2,147,483,647 ์ดํ์ ์์ฐ์์ด๋ค.
www.acmicpc.net
๐ง๐ปโ๐ปํ์ด ๊ณผ์
์ฒ์ ๋ฌธ์ ๋ฅผ ๋ดค์ ๋๋ ๋ฌธ์ ๊ฐ ์ํ๋ ๊ฒ ๋ญ๊ธธ๋ ์ค๋ฒ 1์ผ๊น ์๊ฐํ๋๋ฐ, ์ฃผ์ด์ง ์ซ์ ๋ฒ์๊ฐ ๋ชจ๋ ์ต๋ 2,147,483,647์ด๋๊ตฐ์... ์ฆ,
2๊ฐ์ฉ ๋ฌถ๊ฒ ๋๋ฉด, ๋ค์ ๋ ๊ฐ์ง ์ํฉ์ ์ง๋ฉดํ๊ฒ ๋ฉ๋๋ค.
- B๊ฐ ์ง์์ผ ๊ฒฝ์ฐ
๋จ๋ ๊ฒ ์์ด ๋ชจ๋ ๋ฌถ์ด๋ฏ๋ก ๊ทธ๋๋ก ์งํ - B๊ฐ ํ์์ผ ๊ฒฝ์ฐ
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
์ฆ,
๊ทธ๋ฌ๋ฉด
(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;
}

'Coding Test > 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 |