이 글에서는 주어진 수 N으로 나누어 떨어지는 반복 단위(Repunit)의 최소 길이 k를 구하는 방법을 알아보겠습니다. 반복 단위란 1만으로 이루어진 수를 의미하며, R(k)는 1이 k개 나열된 수를 뜻합니다. 예를 들어 R(4) = 1111입니다. 즉, 우리가 구해야 할 것은 R(k)가 N으로 나누어 떨어지게 만드는 최소의 k입니다.
입력 : N = 13
출력 : k = 6
설명 : R(6), 즉 111111은 13으로 나누어 떨어집니다.
입력 : N = 31
출력 : k = 15
문제 해결 접근 방법
가장 단순한 방법은 k를 1부터 시작해 R(k)가 N으로 나누어 떨어지는지 하나씩 직접 확인하는 것입니다. 하지만 이 방식은 k가 커질수록 R(k) 자체가 기하급수적으로 거대해져 정수 오버플로우가 발생하고, 프로그램이 비효율적이거나 아예 동작하지 않을 수 있습니다.
효율적인 접근 방법
- 먼저 N이 10과 서로소(coprime)인지 확인합니다.
- N이 2 또는 5의 배수라면(즉, 10과 서로소가 아니라면) 어떤 k에 대해서도 R(k)는 N으로 나누어 떨어지지 않습니다.
- 서로소라면 R(1), R(2), R(3)... 각 반복 단위를 N으로 나눈 나머지를 모듈러 연산으로 순차적으로 계산합니다. 이때 실제로 거대한 수를 만들 필요 없이 나머지만 추적하면 됩니다.
- 나머지가 0이 되는 순간의 k가 바로 우리가 찾는 최소 길이입니다. 비둘기집 원리에 의해 서로소인 경우 반드시 유한한 k 내에서 답이 존재함이 보장됩니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int main() {
int N = 31;
int k = 1;
// N이 10과 서로소인지 확인
if (N % 2 == 0 || N % 5 == 0){
k = 0;
} else {
int r = 1; // 현재까지의 누적 나머지
int power = 1; // 10^i mod N
// 나머지가 0이 될 때까지 반복
while (r % N != 0) {
k++;
power = power * 10 % N;
r = (r + power) % N;
}
}
cout << "Value for k : "<< k;
return 0;
}
실행 결과
Value for k : 15
코드 설명
핵심은 변수 r과 power입니다. power는 10의 거듭제곱을 N으로 나눈 나머지를 저장하고, r는 지금까지 계산한 반복 단위 전체를 N으로 나눈 나머지를 누적합니다. 매 반복마다 새로운 자릿수(1)에 해당하는 값을 더하고 다시 모듈러 연산을 적용하기 때문에, k가 아무리 커져도 오버플로우 없이 빠르게 답을 구할 수 있습니다.
마무리
이 글에서는 주어진 N으로 나누어 떨어지는 반복 단위 R(k)의 최소 길이 k를 구하는 문제를 다루었습니다. 단순 완전 탐색 대신 모듈러 연산을 활용한 효율적인 접근법을 소개했고, 이를 C++로 구현한 코드를 함께 살펴보았습니다. 이 로직은 Java, Python, C 등 다른 언어로도 손쉽게 옮겨 작성할 수 있습니다. 이 글이 여러분의 문제 해결에 도움이 되기를 바랍니다.