[C++] 백준 - 4375 : 1

문제 링크

4375번: 1

 

풀이 )

  나머지의 성질을 이용해야한다.

  1로만 이루어진 숫자 tmp는 tmp*10+1씩 커지게 된다.

  매번 연산 시 n에 대하여 나머지 연산을 하게 되면 나머지가 변하지 않게 되므로 큰 수가 필요하지 않는다.

 

#include <iostream>

using namespace std;

int main(void){
    int n;
    while(cin >> n){
        int tmp = 1;
        int cnt = 1;
        while(1){
            if(tmp%n == 0)
                break;
            tmp = (tmp*10+1)%n;
            cnt++;
        }
        cout << cnt << '\n';
    }
    return 0;
}

 

주의 )

  10000이하의 입력에 대해서 최대 결과 값은 입력이 9981일 때 9972로 long long int로도 표현할 수 없는 범위의 값이 나오게 되므로 일단 숫자를 구한 다음에 답을 구하려고하면 오답이 나오게 된다.