나머지연산 공식.

(A + B) % p = ((A % p) + (B % p)) % p
(A * B) % p = ((A % p) * (B % p)) % p
(A - B) % p = ((A % p) - (B % p) + p) % p

(A / B) % p = (A * B^(p-2)) % p = ((A % p) * (B^(p-2) % p)) % p

 

a^b => a^(b/2) * a^(b/2)        // b가 짝수일 경우.

a^b => a^(b/2) * a^(b/2) * a   // b가 홀수인 경우.