쾌속 곱셈 모드

66666666666666666666 * 55555555555555555555555 (17 위) 를 계산 하 라 고 하면 이런 결 과 는 33333333333333333333 33 33 33 33 모델 에 대해 어떻게 계산 할 것 입 니까? 이렇게 2 개의 long long 형의 정수 상승 은 반드시 폭발 할 것 입 니 다. 그래서 우 리 는 빠 른 곱셈 을 도입 하여 계산 합 니 다. 이 알고리즘 의 원 리 는 어 떻 습 니까? 사실은 빠 른 속도 와 차이 가 많 지 않 습 니 다.
예 를 들 어 5 (a) * 8 (b) = 5 * 2 * 2 * 2, 5 * 9 = 5 * 3 * 3 = 5 * (2 + 1) * (2 + 1) 는 이러한 계산 원 리 를 이용 하여 하나의 수 를 끊임없이 2 로 나 누고 하나의 수 를 계속 2 로 곱 하 는 것 이다.
구현 코드:

LL work(LL a, LL b, LL mod)
{
    LL ans = 0;
    while(b) {
        if(b&1) {
            ans += a;
            ans %= mod;
        }
        a *= 2;
        a %= mod;
        b /= 2;
    }
    return ans;
}