최대공약수 최소공배수, 진법

[ 최대공약수 ] 

- 유클리드 호제법을 이용해서 구할 수 있다.

- 두 수 A,B의 최대공약수를 구하려면, A를 B로 나눈 나머지가 r이라고 할 때,

GCD(A, B) = GCD(B, r)  r = 0이 될 때의 B가 최대 공약수이다.

int GCD(int a, int b)
{
	while (b != 0)
	{
		int r = a % b;
		a = b;
		b = r;
	}

	return a;
}

[ 최소공배수 ]

- 다음 관계를 이용하여 푼다.

LCM * GCD = A * B  LCM = A * B / GCD

---

[ N진법 수를 쉽게 10진법 수로 바꾸기 ] 

ex) N = 3진법 수 102를 10진법 수로 바꾸기

왼쪽에서부터 순차적으로 전개해나간다.

102

먼저 가장 왼쪽에 있는 수 1             -> 1

기존 수에 3을 곱하고 0을 더한다.     -> (1 * 3) + 0

기존 수에 3을 곱하고 2를 더한다.     -> (1 * 3 + 0) * 3 + 2 = 11