1627번 곱셈 - C++

✅️[문제]
https://www.acmicpc.net/problem/1629

1629번: 곱셈

✅️[풀이]

재귀 문제이다!
재귀 문제를 풀때에는 수학적 귀납법을 이용하면 된다.
수학적 귀납법은 k=1이 성립하고, k와 k+1이 성립하면 식은 참이 된다.
이 문제에서 b가 1일때 나머지를 구할수 있고, 2b와 2b+1의 나머지를 구할 수 있다. 즉 b가 1일때는 a%c를 리턴하고, b/2를 재귀적으로 호출한다. 이때 b/2가 홀수라면, a를 한번 더 곱하여 나머지를 리턴하고, 짝수라면 그냥 나머지를 리턴하면 된다.

✅️[코드]

#include <bits/stdc++.h>

using namespace std;

#define ll long long

ll ans(ll a, ll b, ll c){

    if(b == 1) return a % c;

    ll val = ans(a, b/2, c);

    val = val * val % c;

    if(b%2 == 0) return val;

    return val * a % c;

}

int main() {

    ios::sync_with_stdio(0);

    cin.tie(0);

    

    int a,b,c;

    

    cin >> a >> b >> c;

    

    cout << ans(a,b,c);

}