| [ QuizWit ] in KIDS 글 쓴 이(By): earny (O___L_) 날 짜 (Date): 2003년 12월 17일 수요일 오후 07시 40분 40초 제 목(Title): Re: [문제] 제곱하였더니... 위에서 하는 방식과 조금 다른 approach로 해봤는데.. 2원 1차 연립 모듈러 방정식으로 표현은 되는데.. 더 나은지는 모르겠습니다. n자리의 경우 문제의 조건을 만족하는 수 a는 다음의 방정식을 만족합니다. a^2 = a (mod 10^n) 이제 이 방정식의 해를 구하면 이 값들이 후보가 됩니다. a^2 = a (mod 10^n) <=> a^2 - a = a * (a-1) = 0 (mod 10^n) <=> a * (a-1) = 0 (mod 2^n) and a * (a-1) = 0 (mod 5^n) <=> a 와 (a-1)은 서로소 이므로 a = 0 (mod 2^n) or a-1 = 0 (mod 2^n) and a = 0 (mod 5^n) or a-1 = 0 (mod 5^n) <=> a = 0 or 1 (mod 2^n) and a = 0 or 1 (mod 5^n) 따라서 답은 다음의 4가지 중 하나를 만족하는 경우입니다. 1) a = 0 (2^n) a = 0 (5^n) 2) a = 0 (2^n) a = 1 (5^n) 3) a = 1 (2^n) a = 0 (5^n) 4) a = 1 (2^n) a = 1 (5^n) 근데 중국인의 나머지 정리에의해 위의 각각을 만족하는 해는 2^n * 5^n 모듈러 안에서 unique합니다. 각각의 경우에 대해 값을 구해보면 1)의 경우는 a = 0 4)의 경우는 a = 1 이므로 한자리 숫자이므로 2자리 이상에서는 답이 될 수 없고, 이제 2) 와 3)을 풀어서 이 값이 n자리인지만 확인하면 됩니다. 근데 2) 와 3)을 풀려면 2^n * x = 1 (mod 5^n) 과 5^n * x = 1 (mod 2^n) 을 풀어야 되는데.. 일반적으로 어떻게 푸는 지를 모르겠네요. 해는 반드시 존재하니깐 컴퓨터로 돌려보면 나오긴 할텐데.. general한 form으로 풀 수 있을까요? 여튼 위의 방정식으로 n = 2, 3일때만 풀어보면 다음과 같습니다. 1) n = 2 일때 4 * x = 1 (25) => x = 19 => a = 4 * 19 = 76 25 * x = 1 (4) => x = 1 => a = 25 * 1 = 25 2) n = 3 일때 8 * x = 1 (125) => x = 47 => a = 8 * 47 = 376 125 * x = 1 (8) => x = 5 => a = 125 * 5 = 625 입니다. 앞분들의 풀이처럼 분명히 뒷부분은 계속 앞에서 구한 답을 포함하네요. |