#4375번 1 (C++)

문제 링크 : www.acmicpc.net/problem/4375

4375번: 1

이 문제는 나머지 연산의 원리를 알아야 시간초과가 안나고 풀 수 있다. 

만약 1부터 11111...1111까지를 대입해서 풀다보면 당연히 시간초과가 날 수 밖에 없다.

 

나머지 연산은 다음과 같다. 

'(A+B)%C와 (A%C + B%C)%C는 같다'

 

위 공식을 해당 문제에 대입하여 풀 경우,

1. N=7

2. 11= (1*10+1)%7

3. ((1%7)*10+1)%7 = 11%7 = 4

4. 111 = (11*10+1)%7

5. (11%7)*10+1 = 40+1 =41%7 = 6

이라는 공식이 성립된다.

 

#include <iostream>
using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n = 0;
    while(cin >> n){
        int temp = 1, cnt = 1;
        while(1){
            if(temp%n==0) break;
            temp = ((temp*10)+1)%n;
            cnt++;
        }
        cout << cnt << "\n";
    }
   return 0;
}