[BOJ] 1323 숫자 연결하기

문제 링크

www.acmicpc.net/problem/1323

풀이

$N$의 길이를 $l$이라고 한다면 $N$에 $N$을 이어붙인 결과는 $N * 10^l + N$으로 표현할 수 있다.
이 값이 $K$로 나누어 떨어지는지 확인하는 것은 법 $K$에 대해 0과 합동인지 확인하는 것과 같다.

따라서, $K$로 나눈 나머지를 이용하여 0이 나올 때까지 계산을 진행하면서 횟수를 세면 된다.
이때 이미 나왔던 수가 다시 등장하면 그것은 $K$의 배수가 될 수 없음을 뜻한다.

Java 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder out = new StringBuilder();

        StringTokenizer st = new StringTokenizer(in.readLine());
        String s = st.nextToken();
        long f = (long) Math.pow(10, s.length());
        int N = Integer.parseInt(s);
        int K = Integer.parseInt(st.nextToken());
        int now = N % K;

        boolean[] vis = new boolean[K];
        vis[now] = true;

        int cnt = 1;
        while (now != 0) {
            now = (int) ((now * f + N) % K);
            if (vis[now]) {
                System.out.println(-1);
                return;
            }
            vis[now] = true;
            ++cnt;
        }

        System.out.println(cnt);
    }
}