문제

문제링크

해설

• 어렵게 생각하면 한없이 어려워질 수 있는 문제입니다.
• 우선 1, 11, 111 … 을 만드는 방법은 1부터 시작해서 10을 곱한 뒤 1을 더하면 됩니다.
• 이 문제의 최대 난관은 ‘어떻게 자료형 오버플로우를 막을 것인가’입니다.
• 주어지는 수는 2와 5의 배수가 아니기 때문에 어떻게든 배수 중 하나로 1로 이루어진 수를 가집니다. 그 수를 x라고 해봅시다.
  • x는 n의 배수이므로, x % n == 0입니다.
  • x % n == 0 이므로 (x % n) % n == 0 입니다.
  • x의 이전 규칙은 ((x / 10) - 1) 인데 이를 x’ 이라고 하면,
  • x % n == (x’ × 10 + 1) % n == ((x’ × 10 % n) + 1) % n 입니다.
• 그러므로 오버플로를 걱정하면서 1, 11, 111, 1111을 계속 만들어가지 말고, n으로 나머지 연산을 하면서 나머지가 0이 나올 때까지 반복문을 반복하면 됩니다.
• 저희는 해당 배수를 구하는 게 아니라, 배수의 자릿수가 궁금한 거니까요.

코드

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n;
    while (cin >> n) {
        int answer = 1;
        unsigned long long temp = 1;
        while (temp % n != 0) {
            temp = ((temp * 10) + 1) % n;
            answer++;
        }
        cout << answer << '\n';
    }
}

소스코드 링크

결과