gcd, lcm, mod

• 최대공약수(GCD, Greater Common Divisor)
  : 두 수가 주어졌을 때, 두 수를 2부터 ~ 두 수 중 작은 수까지 나누어본다. 둘 다 나누어지는 수 중에서 가장 큰 수를 골라 최대공약수를 구할 수 있다. $O(N)$

  • 최대공약수의 약수는 두 수의 약수들이다!

• 최소공배수(LCM, Least Common Multiple)
  : 두 수를 곱하고 최대공약수를 나누었을 때 최소공배수를 구할 수 있다. (최대공약수를 구하는데 $O(N)$이 걸림)

• 모듈러(Mod, Modulo)
  : 나머지 연산. eg) $a = dq + r \Rightarrow r = a \mod d$
  - 모듈러 산술
  $\pm \begin{cases} a = b\mod m \\ c = d\mod m \end{cases} \Rightarrow (a\pm c)=(b\pm d)\mod m$
  $\times \begin{cases} a = b\mod m \\ c = d\mod m \end{cases} \Rightarrow (ac)=(bd)\mod m$

---

유클리드 호제법

• 호제(互除)법 : 두 수가 서로(互) 상대방 수를 나누어(除) 구한다.
• a를 b로 나눈 나머지를 r이라고 했을 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
  ex) $7\%4=3, gcd(7, 4) = 1, gcd(4, 3) = 1$
  → 따라서 이를 연쇄적으로 적용해 (b를 나머지 r로 나눈 나머지 r'을 구하고...), 나머지가 0이 되었을 때 나눈 수가 최대공약수가 된다.

ex) gcd(1112, 156) = ?
	1112 = 156*7 + 20
	156 = 20*7 + 16
	20 = 16*1 + 4
	16 = 4*4 + 0
	-> 4 !

예제

최대공약수, 최소공배수 구하기

백준 2609 최대공약수와 최소공배수

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;

    int gcd, lcm = a*b; // 최소공배수 구하기 = a*b/gcd. a, b가 아래에서 변경되므로 미리 구해줌
    
    while (a%b > 0) { // 유클리드 호제법으로 최대공배수 구하기
        int r = a%b;
        a = b;
        b = r;
    }

    gcd = b; // a%b의 값이 0이 될 때의 b 값이 최대공약수이다.
    lcm = lcm/gcd;

    cout << gcd << "\n" << lcm;

    return 0;
}

(응용) N개의 수를 모두 나누었을 때, 나머지가 같도록 나누는 수 구하기

백준 2981 검문 - [풀이]

트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 
경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다.

상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다.

먼저 근처에 보이는 숫자 N개를 종이에 적는다. 
그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. 
M은 1보다 커야 한다.

N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오.

• 숫자 N개를 3개라고 하고, 수를 {A, B, C} 라고 하자. 문제를 모듈러로 표현해보면 다음과 같다.
  • $r = A \mod M$
  • $r = B \mod M$
  • $r = C \mod M$
• 위 모듈러식을 산술적으로 계산할 수 있다. 식 1, 2를 연립하고 식 2,3을 연립해보면
  • $0 = (B-A) \mod M$
  • $0 = (C-B) \mod M$
• 나머지가 0 이므로 M은 (B-A), (C-B)의 약수가 된다! 즉, (B-A), (C-B)의 최대공약수를 구하고 그 약수를 구하면 정답인 <3개의 수를 나누었을 때, 나머지가 같도록 나누는 수>들을 구할 수 있다.

	// (1) 최대공약수 구하기
    int g = gcd(arr[1] - arr[0], arr[1] - arr[0]);
    for (int i = 1; i < N-1; i++) {
        g = gcd(g, arr[i+1] - arr[i]);
    }
    
    // (2) 최대공약수의 약수 구하기
	for (int i = 1; i*i <= g; i++) {
        if (g%i == 0) {
            m.push_back(i);
            if (g/i != i) m.push_back(g/i);
        }
    }