[BOJ S1][C++] 백준 1629번: 곱셈

https://www.acmicpc.net/problem/1629

1629번: 곱셈

 

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

 

시행착오

짧고 간단한 문제 ㅎㅎ

반복문을 이용하여 쉽게 풀었다ㅎㅎ

// Authored by : seondal
// Co-authored by : -

//#include <bits/stdc++.h>
#include <iostream>

using namespace std;

using ll = long long;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    ll a,b,c;
    cin >> a >> b >> c;
    ll val = 1;
    while(b--) val = val * a % c;
    cout << val;
    
    return 0;
}

/*
 */

 

어림도없지 시간초과~~

 

입력조건이 이미 20억대.... int 범위 이미 넘어버렸다

 

풀이

조금 복잡했지만.. 재귀함수를 이용해서

 

값이 나올때마다 나머지 연산을 미리 해주는 방식으로

값들을 깎아냈다 (?)

 

그 고등학교 제곱 연산때 배우는 공식

a^n * a^n = a^(2n) 

을 사용하였고

 

b가 홀수거나 짝수인 경우만 if 연산 이용해서 처리해줬다

// Authored by : seondal
// Co-authored by : -

//#include <bits/stdc++.h>
#include <iostream>

using namespace std;

using ll = long long;

ll func(ll a, ll b, ll c) {
    if(b == 1) return a % c;
    
    ll tmp = func(a, b/2, c);
    tmp = tmp * tmp % c; // func(a, b, c) 가 연산됨
    
    // b가 짝수면 그대로 리턴, 홀수면 한번 더 곱해주고 연산
    if(b%2 == 1) return tmp * a % c;
    else return tmp;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    ll a,b,c;
    cin >> a >> b >> c;
    cout << func(a,b,c);
    
    return 0;
}

/*
 */

 

조금.. 많이 어려웠다ㅠㅠ

재귀 함수는 일단 직관적으로 납득하기가 힘들어서..

공부 많이 해야할 것 같다