원래 문제 : 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
  • NoSyu 2009.01.11 23:45 ADDR EDIT/DEL REPLY

    재미있네요.^^
    Brute Force로 할 경우 순환마디의 길이를 모르기에 한없이 길어질 수 있는 한계에 도달하는군요.
    (아무런 고민없이 생각해보니...^^;;;; )
    순간 생각하는 프로그래밍에서 소개한 알고리즘이 생각났습니다.
    (전혀 관련이 없겠지만....)
    혹시 좋은 휴리스틱 발견하시면 글 부탁드립니다.^^

    • snowall 2009.01.12 08:58 신고 EDIT/DEL

      네 -_-;
      1/d의 경우 최대 d보다 짧을 것 같다는 생각이 들긴 하지만...;;;

  • daewonyoon 2009.01.12 00:41 ADDR EDIT/DEL REPLY

    1/n 이 순환소수가 된다는 걸 어떻게 증명할까요? 그거 증명하다보면 힌트가 보일 겁니다.

    • snowall 2009.01.12 08:59 신고 EDIT/DEL

      음...유리수의 정의에 의해 자명한지라...생각을 안하고 있었습니다.
      생각해 봐야겠군요.

  • 꼼지락 2009.01.12 00:53 ADDR EDIT/DEL REPLY

    어떤 소수P의 순환소수 마디수 k는 아래와 같습니다.
    10 ** k = 1 (mod P)

    • snowall 2009.01.12 08:59 신고 EDIT/DEL

      이건 소수인 경우에만 해당 되는군요...
      합성수는 어떻게 따질 수 있을까요?

    • 꼼지락 2009.01.12 10:50 신고 EDIT/DEL

      인수에 2와 5가 포함되어 있지 않다면 합성수들도 가능 한 것 같습니다.