[1323] 숫자 연결하기

문제 링크 : https://www.acmicpc.net/problem/1323

1323 - 숫자 연결하기

본문

영훈이는 태형이에게 어떤 수 $N$과 $K$를 주었다.

태형이는 $N$을 종이에 쓰기 시작했다. 태형이는 자신이 이 수를 몇 번 써야 그 수가 $K$로 나누어지는지 궁금해지기 시작했다.

$N=10$일 때, 이 수를 한 번 쓰면 10이고, 두 번 쓰면 1010이고, 세 번쓰면 101010이고,… 이런식이다.

어떤 수 $N$과 $K$가 주어졌을 때, $N$을 몇 번 써야 $K$로 나누어 떨어지는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 $N$과 $K$가 주어진다. $N$은 $1\,000\,000\,000$보다 작거나 같은 자연수이다. $K$는 $100\,000$보다 작거나 같은 자연수이다.

출력

첫째 줄에 몇 번 써야하는지 그 최솟값을 출력한다. 만약 아무리 써도 불가능할 경우에는 $-1$을 출력한다.

제한

시간 제한	메모리 제한
2sec	128MB

---

풀이

어떤 수 $n$이 $k$로 나누어 떨어진다는 것은 $n$을 $k$로 나눈 나머지가 $0$임을 의미한다. $n$을 여러번 이어 붙인 수가 $k$로 나누어떨어지는지 확인하기 위해, 이어 붙인 $n$을 계속해서 계산하기보다는 $n$을 $k$로 나눈 나머지 $a$를 이용하는 것이 좋다. 즉, $n \equiv a \pmod{k}$인 상황에서, $nnnn\cdots{n} \equiv 0 \pmod{k}$이 되도록 하는 것이 문제지만, $nnnn\cdots{n}$을 계산하지 않고 풀어내는 것이 핵심.

두 수 $a, b$가 존재할 때, $a \equiv c \pmod{k}$, $b \equiv d \pmod{k}$라면 아래 식이 성립한다.

\[ab \equiv cd \pmod{k}\]

그리고 이것을 이용하여, 만약 숫자 $n$의 길이가 $l$이라면 숫자를 2번 이어붙인 $nn$의 나머지는 아래와 같이 계산할 수 있다.

\[nn = n \times (10^l + 1) \equiv a \times (10^l + 1) \pmod{k}\]

위 식을 이용하여 나머지를 구해가면 된다. $k$의 범위가 10만 이하이므로, 최대 10만번 $n$을 이어붙여 결과를 계산하면 된다. 만약 그때까지도 이어붙인 수가 $0$으로 나누어떨어지지 않는다면, 그 수는 $n$을 아무리 이어붙여도 $k$로 나누어떨어질 수 없다. $n$을 1번부터 $k$번까지 모두 이어붙인 수의 나머지인 $k$개의 수들 중 같은 수가 존재한다는 것을 의미하게 되고, 어느 순간 반복되는 양상을 띠게 되지만, 그 수들 중 $0$이 없다는 것을 의미하기 때문이다. 이에 대한 이론은 비둘기집 원리 참고.

실제로 답을 구하는 과정을 좀 더 자세하게 설명한다면, 우선 $n$을 $k$로 나눈 나머지 $a$를 계산한다. 그리고 $n$의 길이가 $l$일 때 $10^l$을 $k$로 나눈 나머지 $b$를 계산한다. 그렇다면, 수를 2개 이어붙인다면 그 수의 나머지는 $ab + a \mod k$로 계산할 수 있다. 그리고, 이 과정은 계속 반복할 수 있다. 즉, 이어붙인 수의 나머지 계산이 $O(1)$로 계산이 가능하다.

• 참고 알고리즘 :

코드

사용 언어 : C

최종 수정일 : 2023 / 6 / 22

#include <stdio.h>

int n, k;
long long mod, digit_mod;

long long getDigit(int x) {
    long long r = 1;

    while (x > 0) {
        x /= 10, r *= 10;
    }
    return r;
}

int main() {
    scanf("%d %d", &n, &k);
    mod = n % k, digit_mod = getDigit(n) % k;

    int cur = mod;
    int result;
    for (result = 1; result <= k; ++result) {
        if (cur == 0) {
            break;
        } else {
            cur = (cur * digit_mod + mod) % k;
        }
    }

    if (result > k) {
        printf("-1");
    } else {
        printf("%d", result);
    }
    return 0;
}