C++로 1/n의 순환소수 마침표 길이 구하기

어떤 자연수 n이 주어졌을 때, 1/n을 소수로 전개했을 때 반복되는 숫자 열(순환 마디)의 길이를 구하는 것이 이 문제의 목표입니다. 예를 들어 n = 7이라면 1/7 = 0.142857142857… 이 되며, 굵게 표시된 부분이 무한히 반복됩니다. 따라서 이 경우 마침표의 길이는 6입니다.

접근 방법

n으로 나누는 과정에서 나올 수 있는 서로 다른 나머지는 최대 n가지입니다. 하지만 순환이 반드시 첫 번째 나머지부터 시작하는 것은 아니며, 초반의 일부 나머지는 반복되지 않는 비순환 구간에 속할 수 있습니다.

따라서 순환 구간에 속한 나머지를 확실하게 잡으려면 (n+1)번째 나머지부터 시작해야 합니다. 이 위치에서 출발하여 같은 나머지가 다시 나타나는 지점을 찾으면, 두 지점 사이의 거리가 곧 마침표의 길이가 됩니다.

예제 코드

#include<iostream>
using namespace std;
int periodLength(int n) {
   int remainder = 1;
   int length = 0;
   for (int i = 1; i <= n+1; i++)
   remainder = (10*remainder) % n;
   int d = remainder;
   do {
      remainder = (10*remainder) % n;
      length++;
   } while(remainder != d);
      return length;
}
int main() {
   int n = 7;
   cout << "Period length of 1/"<<n<<" is: " << periodLength(n) << endl;
}

코드 동작 원리

먼저 for 루프를 이용해 총 (n+1)번 나눗셈을 수행하여, 순환 구간 안에 속한 나머지 하나(d)를 얻습니다. 이후 do-while 루프를 돌며 나머지를 계속 갱신하고, 처음 저장해 둔 값 d와 다시 같아질 때까지의 반복 횟수를 세면 그 값이 바로 마침표의 길이입니다.

출력 결과

Period length of 1/7 is: 6