https://www.acmicpc.net/problem/1629
문제
> 자연수 A를 B번 곱한 수를 알고 싶다.
> 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
> 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다.
A, B, C는 모두 2,147,483,647 이하의 자연수이다.접근
A,B,C가 최대 2,147,483,647이므로 최악의 경우만 봐도 계산이 매우 크다는걸 알 수 있다.
따라서 분할 정복을 이용해 재귀로 계산을 작은거부터해서 올라와 준다.
어떤 수의 곱에 대해 밑수가 같으면 지수는 더하기로 구해진다. 예를 들어 3의 4승 x 3의 3승은 3의 7승과 같다.
그렇다면 3의 12승은 3의 6승 x 3의 6승이고 이를 쪼개면 3의 6승은 3의 3승x3의 3승이다. 또 쪼개면 3의 1승 x3의 1승 x3 이다(지수가 홀수면 반 나누준뒤 밑수를 한번 더 곱해주면 된다.) 또 3의 1승은 3의 0승 x 3의 0승 x 3이 된다.
즉, 이 구조는 지수를 반씩 나눠 재귀로 들어가는 형태를 이루고 있고, 이를 거꾸로 보면 3의0승x3의0승x3은 3이므로 이를 이용해 재귀를 깨나가면 각각 3x3x3, 27x27, 등등으로 거듭제곱연산이 아닌 단순 곱셈으로 할 수 있다.
문제해결
> 최대 2,147,483,647이므로 전부 long long 형으로 선언해 처리한다.
> 곱셈을 처리할 메소드 Mul을 정의한다. 입력으로 받은 세 자연수를 인자로 가진다.
> 재귀의 탈출 조건으로 b가 0일 때 1을 반환한다.
b는 지수이므로 a의 b승 즉 a의 0승일 때 이고, 이 값이 1이므로 가장 작은 분할정복 단위로 쓴다.
> b가 1이 아니면 재귀로 1이 될때까지 쪼개줘야한다.
입력받은 b에 대해서 a의 b승은 a의 b/2승 x a의 b/2승인 수학적 규칙을 이용해 재귀로 b를 반씩 쪼개 준다.
> 최종 재귀로 b가 0으로 걸리면 b가 1일 때의 재귀로 돌아오고 재귀의 아랫줄이 실행된다.
> 여기서 값을 계산해준다. 구해온 b/2에대한 a의 b/2승에 대해 이를 곱해 a의 b승으로 만들어준뒤 c로 나눠 나머지를 구한다.
> 이때 b가 홀수라면 b/2했을 때 예를들어 3도 1이고 2도 1이므로 이를 위해 홀수인지 검증을 한 뒤 홀수라면 a를 한번더 곱해주고 c로 나눈 나머지를 다시 계산해준다.
> 다시 처음 재귀로 돌아오면 최종 rst값이 나온다. 코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
long long Mul(long long a, long long b, long long c)
{
if (b == 0) return 1;
long long div = Mul(a, b / 2, c);
long long rst = (div * div) % c;
if (b % 2 == 1) rst = (rst * a) % c;
return rst;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
long long A, B, C;
cin >> A >> B >> C;
cout << Mul(A, B, C) << '\n';
}
후기
처음에 반복문으로 a를 c로 나눈 나머지에 다시 a를 곱하고 c로 나머지를 구하는걸 b번 해봤다. 근데 시간초과가 났다.
그래서 반복문의 횟수를 줄이기 위해 나머지는 어차피 반복되므로 나머지를 인덱스로해 부울형 벡터를 주고 나머지가 이미 true상태면 반복문을 끝내고 나머지의 개수로 b를 나눠 남은 수만큼 n번째 나머지를 출력하도록 했었다. 그랬더니 메모리 초과가 났다. 그렇게 주면 258mb가 필요한데 문제의 최대 메모리는 128mb라서 그렇다.
문제의 태그를 보니 분할 정복문제라고 돼어 있어 이걸 어떻게 쪼갤까 고민하다 풀었다.
