공hannah부
최대공약수(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;
}
'공부 > 알고리즘' 카테고리의 다른 글
거듭제곱 (0) | 2023.08.03 |
---|---|
선형 자료 구조 (배열, 연결 리스트, 스택, 큐, 덱) (0) | 2023.07.31 |
비교 함수 / STL sort (0) | 2023.07.31 |
정렬 (버블정렬, 삽입정렬, 퀵정렬, 병합정렬) (0) | 2023.07.31 |
C++기초, C++ STL (0) | 2023.07.25 |