[백준] 4375 1

문제

n 을 입력받는다.
각 자리수가 1로만 이루어진 n의 배수를 찾는다.
찾은 값 중 가장 작은 값의 자릿수를 출력한다.

각 자릿수가 1로만 이루어진 수 : 1, 11, 111, 1111, …

각 자릿수가 1로만 이루어진 3의 배수 : 111, …
(111은 3의 배수이며 각 자릿수가 1로만 이루어져있다.)

각 자리수가 1로만 이루어진 3의 배수 중 가장 작은 값의 자릿수 : 3
(111의 자리수는 3이다.)

오답의 원인

n이 99999 일 때, 시간초과 또는 런타임에러(out_of_range)가 발생한다.
stoi, stoll, stoull 등을 사용하면 문자열에 저장된 “11111111111111111111” 값이 너무 크기 때문에 변수에 저장할 수 없어 out of range 에러를 던진다.

문제 풀이

1, 11, 111, … 을 n 으로 나누어 떨어지는지 확인하면 된다.
하지만 n이 99999일 때 11111…. 이 너무 커진다는 문제가 있다.
이를 해결하는 것이 이번 문제의 핵심이다.

int n;
cin >> n; 
long long dividend = 1; // 피제수
int cnt = 1; // 피제수의 자릿수
while(1) {
    if(dividend % n == 0) {
        cout << cnt << "\n"; // 정답 출력
        break;
    }
    dividend = dividend * 10 + 1; // 1, 11, 111, ... 을 만드는 반복문
    dividend = dividend % n; // 핵심코드.
    cnt++;
}

위 코드에서 n에 9901이 들어온다고 가정하자.
그럼 dividend = 111111111111 일 때, 반복문을 탈출하게 된다.
dividend 가 longlong 이기 때문에 111111111111 까지는 담을 수 있지만, 만약 n이 99999 면 담을 수 없는 수가 나온다.
dividend를 줄이기 위해선 어떻게 해야할까?

n이 9901 이면 풀이가 너무 길어지니 n에 7이 들어온다고 가정하자.
n = 7 이면, dividend = 111111 일 때 반복문을 탈출하게된다.
$ 111111\ \% 7 = 0 = (11111 * 10 + 1)\ \% 7 $
그럼 위 식을 얻을 수 있다. 위 식을 전개하면 아래와 같은 식이 된다.

식을 모두 전개하면 이전 반복문의 dividend % n이 들어있는 것을 볼 수 있다.
다만 여기서 어떻게 다시 본래 식으로 돌아가느냐가 중요하다.
이는 모듈러 산술의 성질 중 $ x\ mod\ n = (x\ mod\ n)\ mod\ n $ 성질을 이용하면 원래 식으로 돌아갈 수 있다.

즉 최종적으로 위 식이 성립하게 된다.

---

Reference
Pakxe