백준 1323번: 숫자 연결하기

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

 

주어진 수 N, K에 대해서 N을 몇번 이어붙여야 K로 나누어 떨어지는지를 출력하는 문제이다. N의 범위가 커서 단순히 연결만 하면 오버플로우가 발생할 수 있다. 따라서 수를 나눈 나머지를 추적해야 한다.

 

N을 한 번 더 붙인다는 것은 (N * 10^N의 자릿수 + N)  이 되며, 이것의 나머지를 계속 추적하면 된다. 또한, 나머지의 종류는 K가지 이므로 이 연산의 수행 횟수는 K번을 넘지 않는다. 코드는 다음과 같다.

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

public class 숫자연결하기1323 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long n = Long.parseLong(st.nextToken()), k = Long.parseLong(st.nextToken());
        
        long power = 1;
        long temp = n;
        while (temp > 0) {
            power *= 10;
            temp /= 10;
        }
        
        long r = 0;
        long answer = -1;
        
        for (long i = 1; i <= k; i++) {
            r = (r * power + n) % k;
            if (r == 0) {
                answer = i;
                break;
            }
        }
        
        System.out.print(answer);
    }
}