4375

 

문제 요약

 

2와 5로 나누어 떨어지지 않는 정수 n, 각 자릿수가 모두 1로만 이루어진 n의 배수를 찾아라.

 

출력

 

각 자릿수가 모두 1로만 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다.

 

 

문제 풀이

 

뭔소리야?

 

배수는 어떤 수를 다른 수로 나누었을 때 나누어 떨어지는 수를 말한다. 

다른 말로는 한 수를 다른 수로 곱하여 얻어진 수를 해당 수의 배수라고 한다.

 

3, 6, 9는 뭐야? 3의 배수. 왜? 3,6,9라는 수를 3으로 나누었을 때 나누어 떨어지니까.

역으로 3 * 1 =3, 3 * 2= 6, 3*3=9, 얻어진 수는 3,6,9이고 이는 3의 배수.

 

이 개념으로 들어가면 

 

각 자릿수가 1로만 이루어진 경우는 다음과 같다.

1
11
111
1111
11111

 

이를 n으로 나눈 결과가 0인 경우 1xxxx는 n의 배수이다. 

 

주어진 N( 1<= n <= 100000)으로 자리수가 전부 1인 수가 n의 배수인 경우를 찾아야하는데, 생각을 해보자.

 

각 자리의 수가 1인 수를 각 자리를 추가 반복하면서 나누어 떨어지는지 확인해서 결과를 주면된다. 

 

근데 걱정해야하는 부분이 있는데, n이 9901인 경우 각 자리수가 1인 12자리가 발생한다. 

12자리면 100,000,000,000  천억인데, long long 타입으로 가져가도 될 것 같다. 최대 19자리의 정수를 나타낼 수 있다.

만약 부호없는 정수로 표현하면 1자리 더쓸 수 있다.

 

 

응 ~ 시간초과~

#include <bits/stdc++.h>

using namespace std;

int n;
typedef unsigned long long ll;

int main() {

    while(scanf("%d", &n) != EOF){
        ll cnt = 1, ret = 1;
        while(true){
            if(cnt % n == 0) {
                printf("%lld\n", ret);
                break;
            }else{
                cnt = (cnt * 10) + 1;
                ret++;
            }
        }
    }

    return 0;
}

 

모듈로 연산하면 된다. 

#include <iostream>
#include <string>

using namespace std;

typedef unsigned long long ll;

int main() {
    int n;
    while (cin >> n) {
        ll number = 1;
        int digitCount = 1;
        while (number % n != 0) {
            number = (number * 10 + 1) % n;
            digitCount++;
        }
        cout << digitCount << endl;
    }

    return 0;
}