최대공약수(gcd)와 최소공배수(lcm) / 유클리드 호제법

최대공약수와 최소공배수

최대공약수(gcd)

• a=b=0 이 아닌 정수 a,b에 대해, g | a, g | b (a가 g에 나누어 떨어지고, b가 g에 나누어 떨어짐) 을 만족하는 가장 큰 자연수 g

최소공배수(lcm)

• a | l, b | l 을 만족하는 가장 작은 자연수 l

둘 사이의 관계

• 0이 아닌 정수 a, b의 최대 공약수를 g, 최소 공배수를 l이라 할 때, a x b = g x l

---

유클리드 호제법

유클리드 호제법이란?

• 두 자연수 a, b의 최대공약수를 구하는 방법
• 시간복잡도: O(loga)
• 구하는 법
  • 두 자연수 a, b (a >= b) 가 있고, a를 b로 나눈 나머지를 r이라고 할 때
  • gcd(a,b) = gcd(b,r) 이를 r이 0이 될 때까지 반복
  • r이 0일 때 나누는 수가 나누는 수가 a와 b의 최대 공약수이다.

 

• ex) gcd(11,3)
  
  • = gcd(3,2)    ← 이때 2(r)은 11(a)을 3(b)로 나눈 나머지
  • = gcd(2,1)    ← 이때 1은 3을 2로 나눈 나머지
  • =gcd(1,0)     ← r이 0이 되었으므로 반복 종료 / a와 b의 최대공약수는 1

---

C++로 구현해보기

• 반복문

int gcd(int a, int b) {
	int r;
	while(b){     //b가 0이 될 때까지 반복
		r = a % b;
		a = b;
		b = r;
	}
	return a;
}

 

• 재귀문
  • lcm: a x b = g x l이 식을 활용함

int gcd(int a, int b) {
	return b ? gcd(b, a % b) : a;
}

int lcm(int a, int b) {
	return a / gcd(a, b) * b;
}

---

BOJ 17087 숨바꼭질 6

 

문제

수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다.

수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다.

모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자.

 

입력

첫째 줄에 N(1 ≤ N ≤ 105)과 S(1 ≤ S ≤ 109)가 주어진다. 둘째 줄에 동생의 위치 Ai(1 ≤ Ai ≤ 109)가 주어진다. 동생의 위치는 모두 다르며, 수빈이의 위치와 같지 않다.

 

출력

가능한 D값의 최댓값을 출력한다.

---

풀이

수빈이와 동생사이의 거리 % D = 0 이 되어야하므로 모든 동생의 위치에 대해 해당 식을 만족하는 최대 D를 구하려면 

gcd(d1,d2,d3,...,dn)을 구해주어야 한다. 

*여기서 포인트는 처음 ans를 0으로 해줘야 한다는 점!

#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
	return b ? gcd(b, a % b) : a;
}

int main() {
	int n, s, d, ans=0;
	cin >> n >> s;
	vector<int> v(n);

	for (int i = 0; i < n; i++) {
		cin >> d;
		v[i] = abs(s - d);
		ans = gcd(v[i], ans);
	}

	cout << ans;
}