[BOJ] 11819번: The Shortest does not Mean the Simplest

11819번: The Shortest does not Mean the Simplest

풀이

모듈러 연산의 특징 을 알고 있어야 풀 수 있는 문제다(+센스). 여기서는 모듈러의 곱셈, 덧셈 특징이 적용되기에 내용만 적자면 이렇다. 참고: 모듈러 연산 성질

 

곱셈: (A*B) mod C = ((A mod C) * (B mod C)) mod C

덧셈: (A+B) mod C = ((A mod C) + (B mod C)) mod C

 

제곱을 할 때 이것을 써야 하고, 사실 이 문제는 long long 범위를 곱할 때도 그냥 넘겨 버리기 때문에 우리가 쓰는 곱셈을 그냥 쓰면 안 되고 덧셈으로 바꿔서 계산해야 한다. 하지만 일반적인 생각으로 곱셈 구현을 하면 너무 느리기 때문에 a la russe 방식을 쓰면 된다. 

 

'a la russe'나 '빠른 제곱 구하기' 모두 분할 정복을 사용하는 것이다. 

코드

나머지 연산을 곳곳에 박아줬는데 좀 더 줄일 수도 있겠는데 상관 없는 것 같다.

#include <cstdio>
using ull = unsigned long long;

ull A, B, C;
ull mul(ull a, ull b)
{
    ull sum = 0;
    while (a > 0)
    {
        if (a & 1)
            sum += b, sum %= C;
        a >>= 1, a %= C;
        b <<= 1, b %= C;
    }
    return sum % C;
}

ull pow(ull base, ull exp)
{
    if (base == 1)
        return 1;
    ull ans = 1;
    while (exp)
    {
        if (exp & 1)
        {
            ans = mul(ans, base), ans %= C;
        }
        base = mul(base, base), base %= C;
        exp >>= 1, exp % C;
    }
    return ans % C;
}

int main()
{
    scanf("%lld %lld %lld", &A, &B, &C);
    printf("%lld\n", pow(A, B) % C);
    return 0;
}