[백준] C++ 알고리즘 4375번 - 1 문제

 문제

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

4375번: 1

소스코드

#include <iostream>
#include <bits/stdc++.h>
using namespace std; 

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    while (cin >> n) {
        int tmp = 0;
        for (int i = 1; i <= n; i++) {
            tmp = tmp * 10 + 1;
            tmp %= n;
            if (tmp == 0) {
                cout << i << "\n";
                break;
            }
        }
    }
}

풀이

1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.

즉 1,11,111,1111~~~~~~~의 숫자들 중에서 n으로 나누어지는가?

1. (배수인가)

2. 나누어질 때의 가장 작은 자리 수(작은 자리 수 부터 검사해서 나누어지면 정답을 출력하면 되겠죠?)

 

문제는 자리수가 1111111111111111111뭐 이런식으로 될 경우 엄청 긴 자릿수를 저장해야한다.

이런 문제를 해결하기 위해 나머지 연산을 이용한다.

즉 수학문제인데

 

예시로 n이 3일때를 해보자

1은 우선 0*10+1로 표현할수 있다.

1= (0*10+1)%3 = 1

11 = (1*10+1)%3 = ((1%3)*10+1)%3

111 = (11*10+1)%3