[백준] 1629번 - 곱셈 (C++) 문제 및 풀이

문제) 백준 - 분항정복을 이용한 거듭제곱 - 곱셈

-> www.acmicpc.net/problem/1629

1629번: 곱셈

 

중간에 c로 나누어서 수를 작게 만드는게 핵심인 문제. 계산해야할 지수가 홀수,짝수로 나누어 지수법칙 적용.

 

 

 

C++ 소스 코드)

 

	#include <bits/stdc++.h>
	#define endl "\n"
	#define ll long long
	using namespace std;
	ll solve(ll a, ll b, ll c) {
	//기저 사례 처리
	if (b == 0) return 1;
	ll ret = solve(a, b / 2, c);
	if (b % 2 == 1) return ((ret * ret) % c) * a % c;
	else return (ret * ret) % c;
	}
	int main() {
	ios::sync_with_stdio(false);
	cout.tie(0); cin.tie(0);
	ll a, b, c;
	cin >> a >> b >> c;
	cout << solve(a % c, b, c) << endl;
	return 0;
	}

view raw 1629.cpp hosted with ❤ by GitHub