Algorithm 공부 #12 - 정수론(유클리드 호제법과 확장 유클리드 호제법)
Algorithm 공부 #12 - 정수론(유클리드 호제법과 확장 유클리드 호제법)
유클리드 호제법(최대 공약수 구하기)
● 큰 수를 작은 수로 나누는 MOD연산
● 앞 단계에서 나왔던 작은 수와 나머지를 다시 MOD연산
● 이렇게 반복하면서 나머지가 0이 되면 그 순간의 작은 수를 최대 공약수로 선택
ex) 270과 192
270 mod 192 = 78
192 mod 78 = 36
78 mod 36 = 6
36 mod 6 = 0 => 0이 되는 순간 6을 return, 즉 270과 192의 최대공약수는 6
백준 1934번 최소공배수
https://www.acmicpc.net/problem/1934
1934번: 최소공배수
두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있
www.acmicpc.net
※ 유클리드 호제법을 이용하기 ※
● 최소공배수는 두 수의 곱 / 최대공약수
● 두 수의 최대공약수를 유클리드 호제법을 통해 구한 후 두 수의 곱을 최대공약수로 나눠주기
#include<iostream>
using namespace std;
int find(int a, int b);
int main() {
int a, b,n;
cin >> n;
for (int x = 0; x < n; x++) {
cin >> a >> b;
int c = find(a, b);
cout << (a * b) / c<<"\n";
}
}
int find(int a, int b) {
if (a < b)
swap(a, b);
while (b != 0) {
int res = a % b;
a = b;
b = res;
}
return a;
}
백준 1850번 최대공약수
https://www.acmicpc.net/problem/1850
1850번: 최대공약수
모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A
www.acmicpc.net
※ 유클리드 호제법을 이용하기 ※
● 자료형에 주의하기 => long형 사용
● 입력 받은 두 수의 최대공약수의 개수만큼 1을 출력해주면 되는 간단한 문제
#include<iostream>
#include<cmath>
using namespace std;
long gcd(long A, long B);
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long A, B;
cin >> A >> B;
long result = gcd(A, B);
while (result > 0) {
cout << 1;
result--;
}
}
long gcd(long A,long B) {
if (B == 0)
return A;
else {
return gcd(B, A%B);
}
}