분자가 1인 분수를 단위분수라고 합니다. 분모가 2에서 10까지의 단위분수는 아래와 같습니다.

숫자 위에 찍힌 점은 순환마디를 나타내는데, 1/6의 경우 순환마디는 "6"으로 0.166666...처럼 6이 무한히 반복됨을 뜻합니다. 같은 식으로 1/7은 6자리의 순환마디(142857)를 가집니다.

d 를 1000 이하의 정수라고 할 때, 단위분수 1/d 의 순환마디가 가장 긴 수는 무엇입니까?


풀지못했다.
문제만보고 패턴을 찾아보거나 혹은
index를 하나씩 늘려가며 scan하면 되겠거니... 쉽게 생각했는데
소수점 이하의 자리수가 17자리 이상 나오지 않는다.

결국 검색해서 다른 사람이 풀이해 놓은 코드를 보고 구현...그냥 그대로 copy & paste

원리는
나머지가 반복되는 순간을 찾으면 순환마디의 시작을 알 수 있다는 것.
아래 소스도 어느분께서 풀이해놓으신 소스인데.. 링크를 찾지 못 했다. 암튼 이번 문제는 그냥 3개 언어로 구현해봤다는 것으로 만족해야 할 듯..~
 

Python
Ruby
Perl
저작자 표시 비영리 변경 금지
신고
Posted by 용식