Game Develop

나머지연산 공식. 본문

Algorithm/Algorithm

나머지연산 공식.

MaxLevel 2022. 12. 4. 23:28 
(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가 홀수인 경우. 

'Algorithm > Algorithm' 카테고리의 다른 글

MergeSort와 QuickSort  (0) 2022.12.27
음수사이클이 있는 그래프 (다익스트라, 벨만포드, 플로이드와샬)  (1) 2022.12.26
선택,삽입,버블정렬  (0) 2022.10.30
하노이의 탑  (0) 2022.10.30
비트마스크  (0) 2022.08.29
'Algorithm/Algorithm' Related Articles more