๋ณธ๋ฌธ์œผ๋กœ ๋ฐ”๋กœ๊ฐ€๊ธฐ
728x90
๐Ÿ”—๋ฌธ์ œ ๋ณด๋Ÿฌ๊ฐ€๊ธฐ
 

1629๋ฒˆ: ๊ณฑ์…ˆ

์ฒซ์งธ ์ค„์— A, B, C๊ฐ€ ๋นˆ ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. A, B, C๋Š” ๋ชจ๋‘ 2,147,483,647 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋‹ค.

www.acmicpc.net

 

๐Ÿง‘๐Ÿป‍๐Ÿ’ปํ’€์ด ๊ณผ์ •

์ฒ˜์Œ ๋ฌธ์ œ๋ฅผ ๋ดค์„ ๋•Œ๋Š” ๋ฌธ์ œ๊ฐ€ ์›ํ•˜๋Š” ๊ฒŒ ๋ญ๊ธธ๋ž˜ ์‹ค๋ฒ„ 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;
}

 

728x90
๋ฐ˜์‘ํ˜•