[BOJ] ๊ณฑ์…ˆ(1629)

[๋ฐฑ์ค€(BOJ)] ๊ณฑ์…ˆ(1629) C++

๋ฌธ์ œ : BOJ_1629๋ฒˆ ๊ณฑ์…ˆ

๋ฌธ์ œ ์„ค๋ช…

๋ถ„ํ• ์ •๋ณต

A, B, C๊ฐ€ ์ฃผ์–ด์ง€๊ณ  , A๋ฅผ B๋ฒˆ ๊ณฑํ•œ ๊ฐ’์„ C๋กœ ๋‚˜๋ˆˆ ๊ฐ’์˜ ๋‚˜๋จธ์ง€๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.
B๊ฐ€ ๋งค์šฐ ํฌ๊ธฐ ๋•Œ๋ฌธ์—, B์— ๋งž๊ฒŒ ์—ฌ๋Ÿฌ ๋ฒˆ ๊ณฑํ•ด์ฃผ๋ฉด ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๋‚ฉ๋‹ˆ๋‹ค.


Solution

n์ด ์ง์ˆ˜๋ผ๋ฉด, A^n = A^(n/2) * A^(n/2) n์ด ํ™€์ˆ˜๋ผ๋ฉด, A^n = A^(n/2) * A^(n/2) *A์ธ ๊ฒƒ์„ ์ด์šฉํ•˜์—ฌ ๋ถ„ํ•  ์ •๋ณต ํ•ฉ๋‹ˆ๋‹ค.
๊ฐ’์˜ ํฌ๊ธฐ๋„ ์ด ๋ฌธ์ œ์—์„œ ๋งค์šฐ ์ค‘์š”ํ•œ๋ฐ, A, B, C์˜ ๊ฐ’์ด intํ˜•์˜ ์ตœ๋Œ“๊ฐ’๊นŒ์ง€ ๊ฐ€๋Šฅํ•˜๋ฏ€๋กœ, long longํ˜•์œผ๋กœ ํ•ด์ฃผ๊ณ ,
mod C๋ฅผ ๊ณ„์† ์ˆ˜ํ–‰ํ•ด ์ฃผ์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.
๊ทธ๋ฆฌ๊ณ  ์ €๋Š” ์ด ๋ฌธ์ œ์—์„œ ์ž๊พธ ์˜ค๋‹ต ์ œ์ถœ์ด ๋งŽ์ด ๋๋Š”๋ฐ, n์ด ํ™€์ˆ˜์ผ ๋•Œ A^n = A^(n/2) * A^(n/2) *A์ธ ์กฐ๊ฑด์—์„œ,
(A^(n/2)*A^(n/2)*A) ๋ฅผ ๊ทธ๋Œ€๋กœ ๋ฌถ์–ด์„œ mod C๋ฅผ ํ•ด์ฃผ๋ฉด, ์„ธ ๊ฐœ์˜ ์‹์ด ๊ณฑํ•ด์ง€๋Š” ๋™์•ˆ ์ด๋ฏธ ์˜ค๋ฒ„ํ”Œ๋กœ์šฐ๊ฐ€ ๋ฐœ์ƒํ•  ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ
์˜ค๋‹ต ์ฒ˜๋ฆฌ๊ฐ€ ๋์Šต๋‹ˆ๋‹ค. ((A^(n/2) _ A^(n/2))%C _ A) % C ์™€ ๊ฐ™์€ ์‹์œผ๋กœ, ๋‘ ์ˆ˜๋ฅผ ๋จผ์ € ๊ณฑํ•˜๊ณ  mod C๋ฅผ ํ•ด์ฃผ๋Š” ๊ฒƒ์ด ์ค‘์š”ํ•ฉ๋‹ˆ๋‹ค.


Description

  1. ๋ฌธ์ œ์— ๋‚˜์˜ค๋Š” ๋ชจ๋“  ๋ณ€์ˆ˜์™€ ํ•จ์ˆ˜์˜ ๋ฐ˜ํ™˜๊ฐ’ ๋ฐ ์ธ์ž๋ฅผ ๋ชจ๋‘ long longํ˜•์œผ๋กœ ์ฒ˜๋ฆฌ
  2. ์žฌ๊ท€์˜ ํ˜•์‹์œผ๋กœ ๊ณฑํ•ด์ง€๋Š” ํšŸ์ˆ˜๊ฐ€ 1์ผ ๋•Œ๊นŒ์ง€ ๋‚ด๋ ค๊ฐ€๋Š” ํ•จ์ˆ˜๋ฅผ ์‚ฌ์šฉ

#include <iostream>
using namespace std;
long long A, B, C;
long long func(long long val, long long num);
// val -> ๊ณฑํ•ด์ง€๋Š” ๊ฐ’, num -> ๊ณฑํ•ด์ง€๋Š” ํšŸ์ˆ˜
int main(void) {
	cin >> A >> B >> C;
	A = A % C;
	long long result = func(A, B) % C;;
	cout << result << '\n';
}
long long func(long long val, long long num) {
	if (num == 1) return val % C;
	long long nowVal = func(val, num / 2) % C;
	if ((num % 2) == 0) return (nowVal * nowVal) % C;
	else return ((nowVal * nowVal % C) * val) % C;
	// ์˜ค๋ฒ„ํ”Œ๋กœ์šฐ๋ฅผ ๋ฐฉ์ง€ํ•˜๊ธฐ ์œ„ํ•ด %C๋ฅผ ๋‘ ๋ฒˆ ํ•ด์ค€๋‹ค.
}