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번: 최소공배수

 

※ 유클리드 호제법을 이용하기 ※

● 최소공배수는 두 수의 곱 / 최대공약수

● 두 수의 최대공약수를 유클리드 호제법을 통해 구한 후 두 수의 곱을 최대공약수로 나눠주기

 

#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번: 최대공약수

 

※ 유클리드 호제법을 이용하기 ※

● 자료형에 주의하기 => 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);
	}
}