(C++) [백준 1629번] 곱셈

 

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

1629번: 곱셈

가장 간단하게 생각하는건 a를 b번 곱한다음 c로 나눈 나머지를 구하는건데, 범위가 2^32-1이라 BIGINTEGER나 __int128같은 자료형을 쓰지 않는 이상(아니 아마 쓰더라도) 오버플로가 날거고, a에 a를 곱하고 c로 나눈 나머지에 다시 a를 곱하고 c로 나눈 나머지를 구하고...로 구한다고 하더라도 b번 곱하는데 O(b)면 시간초과가 날것이다.

 

이 문제는 바킹독님 강의의 이 부분을 참고해서 풀면 도움이 많이 된다.

12^58 % 67 = 4, 12 ^ 116 % 67 = 16이랑 k승을 계산했으면 2k승과 2k+1승도 O(1)에 계산할 수 있다는 말이 핵심이다.

((a^k)%c * (a^k)%c) % c == a^2k%c이고, ((a^k)%c*(a^k%c)*a) % c == a^2k+1%c이므로, 이를 이용해

b가 짝수일때, 홀수일때로 나누어서 계산해주면 된다.

#include <iostream>
using namespace std;
#define ll long long
ll x, y, z;
ll mul(ll a, ll b, ll c)
{
    if (b == 1)
        return a % c;
    ll tmp = mul(a, b / 2, c) % c;
 
    if (b % 2 == 0)
        return (tmp * tmp) % c;
    else return ((tmp * tmp)%c * a) % c;
}
int main()
{
    cin.tie(0); ios::sync_with_stdio(0);
    cin >> x >> y >> z;
    cout << mul(x, y, z);
}