[C++][BOJ 나머지(10430)] 유클리드 호제법

백준 10430 바로가기

 

문제 자체는 쉽지만 다음에 풀 문제들을 위해 유클리드 호제법과 함께 같이 기록해놓는다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;
int main(){
	int a,b,c;
	scanf("%d %d %d",&a,&b,&c);
	printf("%d\n%d\n%d\n%d", (a+b)%c, ((a%c)+(b%c))%c, (a*b)%c, ((a%c)*(b%c))%c );
	return 0;
} 

 

---

유클리드 호제법이란?

두 수의 최대 공약수를 구하는 알고리즘의 하나.

 

2개 자연수 a, b ( a > b )에 대해 a를 b로 나눈 나머지를 r이라 하면,

a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

또 다시 b , r 에 대해 b를 r로 나눈 나머지 r' 을 가지고 위의 과정을 반복해 나머지가 0이 되었을 때

나누는 수가 a와 b의 최대 공약수.

 

( a , b ) = ( b , r )  = ( r , r' )

 

( 1071 , 1029 ) = ( 1029 , 42 ) = ( 42 , 21 ) = ( 21 , 0 ) = 21

21은 1071과 1029의 최대 공약수

 

알고리즘

1. a , b (a > b) 가 입력으로 들어온다.

2. b == 0 이면 a 리턴 

3. 아니라면  b ,a%b 로 다시 반복

 

소스 코드

//recursive 
int GCD1(int a,int b){
	return b? GCD(b,a%b) : a;
} 

int GCD2(int a, int b){
	int tmp;
	while(a%b){
		tmp = a/b;
		b = a%b;
		a = tmp;
	}
	return a;
}

더 자세한 유클리드 호제법 알고리즘

 

 

참고 페이지

위키-유클리드호제법