백준 1629번: 곱셈

백준 1629번: 곱셈

1629번: 곱셈

 

처음에 무작정 재귀함수를 쓰려다가 최고값으로 돌려보았을 때 연산시간이 너무 길어진다는 것을 알았다.

그래서 고민해보다가 방법을 모르겠어서 결국엔 구글링... 알고리즘 자체는 간단했다.

입력값 B를 계속해서 분할하여 제곱 계산법으로 풀어나가는 것이었다.

 

B가 10이라고 가정하면

A^10 => (A^5)^2 => ((A^2)^2*A)^2 => (((A)^2)^2*A)^2

 

B가 더이상 안나눠질 때까지 반복해 쪼갠뒤 1부터 시작하게했다.

알고리즘 이해 자체는 간단했으나 시간초과도 아니고 자꾸 틀렸습니다가 뜨는것이다.

C로 나눈 나머지 값들을 계산하는 변수에 저장해서 최대값 이내에서 다 해결되는 줄 알았는데 아니었나보다.

결국 재귀 함수와 계산 값을 저장하는 res 변수에 long long을 선언하여 해결했다.

 

#include<iostream>
using namespace std;

int C;
long long mult(int A, int B){
    if(B == 0) return 1;
    long long res = mult(A, B/2);
    if(B % 2 == 0) return (res*res)%C;
    else return ((res*res)%C*A)%C;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int A, B;
    cin >> A >> B >> C;
    cout << mult(A%C, B) << "\n";
    return 0;
}