프로젝트 오일러 26. Reciprocal cycles

요즘은 오일러 도장깨기에 맛들렸다. 간혹가다 흥미로운 문제가 있다.

 

26번의 경우, 1/n을 소수로 나타냈을 때 반복되는 마디의 수를 구하는 것이 핵심이다.

 

나눗셈 과정을 역추적하면 이를 구할 수 있는데, 가령 1/14의 마디 수를 구하려면

 

1 % 14 = 1

10 % 14 = 10

100 % 14 = 2

20 % 14 = 6

60 % 14 = 4

40 % 14 = 12

120 % 14 = 8

80 % 14 = 10

 

반복되는 마디가 6개이므로, 마디의 길이는 6임을 알 수 있다.

하지만 이 방법을 사용하려면 각 나머지별로 출현했는지 여부를 저장해야 하므로, O(n)의 메모리 공간이 필요하다.

 

조금 더 좋은 방법이 있을까?

흥미로운 방법이 있는데, n자리가 반복되는 수는 모두

$\frac{x}{99...9900...00}$의 꼴로 나타낼 수 있는 점에 착안한 방법이다. 여기서 9의 갯수는 n개이고, 0의 갯수는 상관없다.

 

이 경우 $\frac{1}{n} = \frac{x}{99...9900...00}$에서 $99...9900...00$가 n의 배수가 되어야 한다는 것을 알 수 있다.

결국 n에서 소인수 2와 5를 제거한 값의 배수가 되는 최소의 999...999를 찾으면 되는 문제로 변한다. 이 방법을 사용하면 별도의 메모리 공간이 필요없다.