[백준] 1629.cpp : 곱셈

www.acmicpc.net/problem/1629

1629번: 곱셈

---

• 모듈러 연산의 성질을 이해해야 한다.
• (A * B) % C == ((A % C) * (B % C)) % C
• 다만 B 의 범위가 21억까지이기 때문에, 전부 곱할 수는 없으므로 재귀를 통하여 반씩 나눠서 곱해준다.
• 연산 결과에 대한 자료형의 범위에 대해서도 주의할 것.

---

#include <iostream>

#define ull unsigned long long
#define pow(x) ((x) * (x))

ull a, b, c; 

ull mod(ull s)                  // 분할 정복
{
    if(s == 1)  return a % c;   // 1일 경우는 종료
    else        return ((pow(mod(s / 2) % c) % c) * (s % 2 == 0 ? 1 : (a % c))) % c;
}                               // 그 외에는 제곱수를 반으로 나눠서 곱해줌
                                // ex a^91 -> a^45 * a^45 * a
                                // ex a^80 -> a^40 * a^40

int main(void)
{
    std::cin >> a >> b >> c;
    std::cout << mod(b) << '\n';
}