[C++]4375번 : 1

문제 : https://www.acmicpc.net/problem/4375

4375번: 1

 

이 문제 역시 로직 자체는 간단하다. 입력받은 수로 영원히 나누어 떨어지지 않는 경우에 대해서는 아무 언급이 없으므로 항상 나누어 떨어진다고 취급할 수 있고, 따라서 1을 무한히 늘려 가며 나누어 떨어지는 순간 해당 숫자의 길이를 출력하면 된다.

1을 늘리는 방법에는 여러 가지가 있겠지만, 가장 간단한 방법은 원래 수 * 10 +1을 하면 된다.

하지만 숫자의 표현 범위에는 한계가 있으므로, 아무런 처리 과정 없이 1을 계속 늘리면 표현 범위를 초과하게 된다. 따라서 long long의 범위를 초과하지 않는 선에서 값을 구하는 것이 이 문제의 요지이다.

 

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    long long l;
    while(scanf("%d", &n) != EOF){
        l = 1;
        while(l%n!=0){
            l = (l*10+1)%n;
        }
        cout << to_string(l).length() << endl;
    }
}

이 문제는 입력 데이터의 갯수를 입력받지 않으므로, 자체적으로 입력을 종료해야 한다. scanf로 매번 데이터를 입력받고, 더이상 입력받을 데이터가 없으면(EOF) 반복을 종료한다.

로직은 위에서 설명한 것과 동일하게 수행되지만, 한 가지 차이가 있다.

이전 값이 나누어 떨어지지 않으면, 1을 그냥 붙이는 것이 아니라 1을 늘린 다음 나눈 나머지 값을 저장한다. 모듈로 사칙연산의 분배 법칙에 의해 이와 같은 풀이 방식이 성립된다.