원래 문제 : http://projecteuler.net/index.php?section=problems&id=26

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아닌가?
!$^$%@#$^@#%&@$%*@%^@#$%.....

꼬였다.

누가 힌트좀 주세요. -_-;
by snowall 2009. 1. 11. 16:55