본인 풀이

모듈로 연산 관련 공식을 까먹어서 그냥 바로 답안 확인했음

답안 및 로직

1. 재귀적으로 제곱하면 시간복잡도가 O(N)에서 O(logN)으로 줄어든다. 로그의 밑은 2
2. 모듈로 연산관련 공식은 다음과 같다.
   1. (a+b) % c == ((a%c) + (b%c)) % c
   2. (a*b) % c == (a%c * b%c) % c이다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, c;

ll solution(ll a, ll b){
    if (b==1){
        return a % c;
    }

    ll ret = solution(a, b / 2);
    ret = (ret * ret) % c;

    // 홀수제곱 처리
    if (b % 2) {
        ret = (ret * a) % c;
    }
    return ret;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> a >> b >> c;

    ll ret = solution(a, b);
    cout << ret << "\n";

    return 0;
}

1. long long 타입을 사용한다.
2. solution 기저사례로 A%C 값을 넣어둔다.
3. 정수론 공식을 코드로 작성하고, 홀수처리만 추가로 진행한다.

복습 (7/17)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, c;

ll solution(int size){
    if(size == 0){
        return 1;
    }
    if(size == 1){
        return a % c;
    }
    if(size % 2 == 1){
        return ((a % c) * solution(size / 2) % c * solution(size / 2) % c) % c;
    }else{
        return (solution(size / 2) % c * solution(size / 2) % c) % c;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> a >> b >> c;

    cout << solution(b) << "\n";
    return 0;
}

1. 재귀로 풀이
2. 홀/짝 분기만 처리하고, size/2로 접근하여 log기반 복잡도로 풀이