JArchive 프로그래밍 일기

문제

곱셈 백준 1629

"맞았습니다" 코드

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

ll A, B, C;

ll rec(ll a, ll b, ll c){
  if(b == 1) return a % c; // a가 c보다 클 수 있기 때문에 a % c를 반환.
  ll val = rec(a, b/2, c);
  val = val * val % c;
  if(b%2 == 0) return val; 
  return val * a % c; // b가 홀수라면 *a %c 를 한 번 더 수행. 
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> A >> B >> C;
  cout << rec(A, B, C);
  return 0;
}

리뷰

재귀를 공부하면서 푼 문제다.
곱셈을 하면 int의 범위를 넘어서기 때문에 long long 을 써야 한다.
단, b승을 알려면 b/2승을 제곱하면 된다는 것을 기반으로 코드를 짜야 한다.