1로만 구성된 숫자를 repunit이라 부른다. R(k)를 길이가 k인 repunit으로 정의하자. 예를 들어, R(6)=111111이다.
gcd(n,10)=1인 양의 정수 n에 대해 언제나 R(k)를 n으로 나눌 수 있는 k가 존재한다. 그러한 k 중 최소값을 A(n)이라 하자. 예를 들어, A(7)=6이고, A(41)=5이다.
A(n)이 10을 초과하는 최초의 n은 17이다.
A(n)이 1백만을 초과하는 최초의 n을 구하시오.
--------------------------------------------------------------------------
문제를 조금 부연설명하면 gcd(n,10)=1이라 했으므로, n은 2, 5와 공약수가 없는 숫자이다(2와 5로 나눠지지 않는다). 이것만 가지고 구현했을 때 예시에서 나온 A(7), A(41)이나 결과가 10이 넘는 A(n)의 값은 쉽게 구할 수 있는데, 결과가 1백만을 초과하는 것을 구하려면 시간이 대책없이 필요했다.
처음 2부터 입력해서 나온 n, k의 결과값 목록을 보면서도 생각하지 못했는데, 오일러 프로젝트를 풀고 있는 다른 블로거의 설명을 보고 빨리 해결하는 방법을 구할 수 있었다.
중요한 단서는 k가 n보다 클 수 없다는 것이다. 그것을 보고 시작지점을 변경해서 빠른 시간 내에 답을 구할 수 있었다.