BestCoder #80 - 1002 빠른 곱셈 모드

제목 링크: BestCoder #80 - 1002 Segment
처음에는 너무 막막했는데 나중에 x+y=q를 발견했어요. 그리고 y=(q-i)/i*x를 간략하게 하면 (x+y)=q/i예요.그러면 제목의 묘사에 따르면 q는 질수이기 때문에 q/i로 말하자면 i=1이거나 i=q이다. 이 두 가지는 모두 x+y=q에 꼭 맞기 때문에 이런 라인은 아무런 영향이 없다.
코드: View Source On GitHub
새로운 것을 배웠다: 빠른 곱셈으로 모형을 뽑다
연결: 빠른 곱셈/멱 알고리즘 설명
코드는 다음과 같습니다.

long long q_mul( long long a, long long b, long long mod ) //     (a*b) % mod
{
    long long ans = 0;  //    
    while(b)                //  b          a
    {
        if(b & 1)           //      1
        {
            b--;
            ans =(ans+ a)%mod;   //ans+=a
        }
        b /= 2;                         //b    
        a = (a + a) % mod;          //  a

    }
    return ans;
}

나는 이미 AC 제목의 소스 코드를 저장하기 위해 GitHub에 창고를 만들었다.수록되지 않은 제목이나 더 좋은 해법이 있다면 포크창고+PR을 환영합니다~ AC코드 집중창고를 공동으로 만들어서 ACM Beginner를 행복하게 해주세요~
창고 주소: OJ-Problems-Source On GitHub