유클리드 호제법 (정의, 원리, 증명)
1. 정의A = Bq + R일 때, A와 B의 최대공약수 G는 B와 R의 G와 같다. 를 활용하여, 연쇄적인 나눗셈으로 A,B의 최대공약수를 구하는 방법을 말한다. 2. 원리정의에서 연쇄적인 나눗셈이라고 한 이유는 다음과 같다. 1. A = Bq + R 2. B = Rq + R'3. R = R`q + 0 간단하게 3번안에 끝나는 예시를 보자. A,B의 G는 B,R의 G와 같음.B,R의 G는 R,R'의 G와 같음.마지막 식에서 나머지가 없으므로, R'는 R의 약수임. R과 R'의 최대 공약수는 당연하게도 R'임. 이제 연어처럼 3 -> 1로 거슬러 올라가면 종국에 A,B의 최대공약수는 R'랑 같음.3. 증명(1) A와 B와 R이 같은 G를 공유하는가?A = Ga, B = Gb (G가 최대공약수임으로, a와..
더보기
[백준] 6064 카잉 달력 java 풀이
1. 문제 설명문제 링크이란 달력이 있는데, (x,y) -> (1,1) , (2,2) 가다가 x가 M을 넘거나, y가 N을 넘으면 다시 1로 돌아온다.예제에 설명되어 있는 대로, 일때, 13번째 년도는 이 된다. , , , 순으로 온다.문제에서 M,N,x,y를 줄 때, 달력에서 가 몇 번째 년도인지 구하라.2. 접근 방식이것도 도저히 생각이 안나서 다른 사람 풀이 봤다. (요즘 왜 이렇게 풀이가 생각이 안나지? 더 열심히 해야겠다.)KEY WORD: 유클리드 호제법, LCM과 GCD의 관계먼저 ~ 까지 순서대로 번호를 매긴다고 해보자. 이때 우리가 구해야하는 는 K번째 수라고 해보자.x는 K를 M으로 나누었을 때의 나머지이고, y는 K를 N으로 나누었을 때 나머지 이다.에서 는 33번째 수인데,..
더보기
