글
원래 문제 : http://projecteuler.net/index.php?section=problems&id=26
1을 자연수 n으로 나누면 유리수다. (당연히!) 예를 들어...
여기서 (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아닌가?
!$^$%@#$^@#%&@$%*@%^@#$%.....
꼬였다.
누가 힌트좀 주세요. -_-;
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아닌가?
!$^$%@#$^@#%&@$%*@%^@#$%.....
꼬였다.
누가 힌트좀 주세요. -_-;
RECENT COMMENT