1을 자연수 n으로 나누면 유리수다. (당연히!) 예를 들어…
|
1 / 2 |
= | 0.5 |
|
1 / 3 |
= | 0.(3) |
|
1 / 4 |
= | 0.25 |
|
1 / 5 |
= | 0.2 |
|
1 / 6 |
= | 0.1(6) |
|
1 / 7 |
= | 0.(142857) |
|
1 / 8 |
= | 0.125 |
|
1 / 9 |
= | 0.(1) |
|
1 / 10 |
= | 0.1 |
여기서 (6)은 무한히 반복됨을 뜻한다. (142857)은 142857이 무한히 반복된다는 뜻이다.
가령, 1/6은 1자리의 순환 마디를 갖고 있다. 1/7은 6자리의 순환 마디를 갖고 있다.
문제 : 1부터 1000까지의 자연수 중, 1/d가 가장 긴 순환 마디를 갖게 되는 자연수 d를 찾아라.
이 문제를 풀기 위해서 고민을 하는데, 도저히 방법이 안보인다. 지금까지 푼 29개의 문제는 어떻게든 (시간이 오래 걸리더라도) 풀긴 했는데, 이건 수가 없다.
일단 알아낸 것 – d가 2나 5만을 인수로 갖는다면 그냥 넘어가도 된다. 확실하게 유한소수니까.
고민해본 방법 1
1/d=x라고 하자. x, 10x, 100x, 1000x…이런 식으로 10을 곱해나간다. 그리고, 10x-x, 100x-x, 1000x-x등등을 계산해서 정수로 떨어지면 그때까지 반복한 회수를 세면 된다
문제점 – 1/6을 처리할 수 없다. -_-;
고민해본 방법 2
그래서. 10x-x, 100x-x, …를 계산하고, 그때마다 10, 100, 1000…을 곱해서 정수로 떨어지게 만들어 보려고 했다.
문제점 – 어느세월에 끝나나…
고민해본 방법 3
순환마디의 특징을 고찰해 보자.
x=0.abcde…(xyz) 이런 식으로 되어 있다.
어릴 적에 배운 기억을 되짚어 본다.
이런 걸 풀기 위해서는 x에다가 최초의 순환마디가 끝나는 데 까지의 자리수만큼인 10^m을 곱한 숫자에서 최초로 순환마디가 나오는 데 까지의 자리수만큼인 10^n을 곱한 숫자를 뺀다.즉 x(10^m-10^n) 을 계산한다고 들었다. 근데 어차피 내가 필요한 숫자는 m-n아닌가?
!$^$%@#$^@#%&@$%*@%^@#$%…..
꼬였다.
누가 힌트좀 주세요. -_-;
인수에 2와 5가 포함되어 있지 않다면 합성수들도 가능 한 것 같습니다.
이건 소수인 경우에만 해당 되는군요…
합성수는 어떻게 따질 수 있을까요?
음…유리수의 정의에 의해 자명한지라…생각을 안하고 있었습니다.
생각해 봐야겠군요.
네 -_-;
1/d의 경우 최대 d보다 짧을 것 같다는 생각이 들긴 하지만…;;;
어떤 소수P의 순환소수 마디수 k는 아래와 같습니다.
10 ** k = 1 (mod P)
1/n 이 순환소수가 된다는 걸 어떻게 증명할까요? 그거 증명하다보면 힌트가 보일 겁니다.
재미있네요.^^
Brute Force로 할 경우 순환마디의 길이를 모르기에 한없이 길어질 수 있는 한계에 도달하는군요.
(아무런 고민없이 생각해보니…^^;;;; )
순간 생각하는 프로그래밍에서 소개한 알고리즘이 생각났습니다.
(전혀 관련이 없겠지만….)
혹시 좋은 휴리스틱 발견하시면 글 부탁드립니다.^^