정수론 (1)

[알고리즘] 정수론

• 유클리드 알고리즘(Euclidean algorithm)
1. 정의: 두 수의 최대공약수를 구하는 방법
2. 구현 방법: 파라미터로 a와 b를 받고, b=0이면 a를 반환한다. 아닐 경우, b와 a를 b로 나눈 나머지(a % b)를 인수로 재귀함수를 호출한다. a = b * R1 + 2, b = R1 * R2 + R3, ... , R(n-2) = R(n-1) * Rn + 0 일 때, Rn이 최대공약수이다.
3. 구현:

int gcd(int a, int b){
    if(b == 0) return a;
    else return gcd(b, a % b);
}

• 모듈라 연산

1. 정의: 모듈로(modulus) M에 도달하면 다시 0으로 돌가는 정수들을 가지고 하는 연산. 
2. 덧셈, 뺄셈, 곱셈

(a + b)%M = ((a%M) + (b%M))%M

(a - b)%M = ((a%M) - (b%M) + M)%M

(a x b)%M = ((a%M) x (b%M))%M

• 참고 문제: [POTION] 마법의 약 http://yejin0730.tistory.com/4