문제
K자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
출력
첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.
정답코드
#include<bits/stdc++.h>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n'
using namespace std;
long long powl(long long a, long long b, long long c)
{
if(b==0) return 1;
long long total = powl(a, b/2,c)%c;
long long temp = total * total%c;
if(b%2==0) return temp%c;
else return a * temp%c;
}
int main()
{
FASTio;
int a,b,c,total=1;
cin >> a >> b >> c;
cout << powl(a,b,c) << endl;
return 0;
}
풀이 및 사고과정
일단 밑과 지수가 전부 21억이 넘기 때문에 4byte인 int로는 처리가 불가능하다. 하물며 계속계속 제곱을 해나가면 결국 오버플로우가 나기 때문에 이 부분을 모듈러 연산과 long long으로 잘 처리해줘야한다.
제곱을 하는 방법은 두가지가 있는데 첫번째로는 1차원적으로 a를 b번 곱하면 될 것이다. 근데 이 방법으로는 시간이 무수히 많이 걸리기 때문에 다른 방법을 생각해내야한다.
두 번째 방법은 제곱의 특성을 활용하여 분할해서 문제를 해결하는 방법이다.
예를 들어 2^8은 2^4 * 2^4로 표현할 수 있고 이런 식으로 쪼개서 가다보면 똑같은 수를 한 번 더 계산하지 않아도 되기 때문에 'logN'번 만에 계산이 가능하다.
...