[백준][C++] 1629: 곱셈

문제 링크: https://www.acmicpc.net/problem/1629

 

모듈러 연산의 성질과 분할 정복을 이용한 거듭제곱을 사용해 푸는 문제입니다.

\[(a\times b)\%M = ((a\%M) \times (b\%M))\%M\]

위 식과 분할정복 방법을 적당히 섞어주면 됩니다

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING

#include <bits/stdc++.h>
using namespace std;


typedef long long ll;

ll binpow_mod(ll a, ll b, ll mod) {
	ll res = 1;

	while (b > 0) {
		if (b & 1)
			res = (res * a) % mod;

		a = (a * a) % mod;
		b >>= 1;
	}

	return res;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	int a, b, c;
	cin >> a >> b >> c;

	cout << binpow_mod(a, b, c) << '\n';

	return 0;
}

저번에 올린 binpow 함수를 약간 수정했습니다. base를 제곱할 때 mod 연산을 하고, 결과값에 곱할 때도 mod 연산을 썼습니다.