싸이클_2526

두 자연수 N과 P를 가지고 다음 과정을 거쳐서 나오는 수를 차례대로 출력해보자. 처음 출력하는 수는 N이고, 두 번째 이후 출력하는 수는 N을 곱하고 P로 나눈 나머지를 구하는 과정을 반복하여 구한다. 즉, 먼저 N에 N을 곱하고, 이 수를 P로 나눈 나머지를 두 번째에 출력한다. 다음에는 이 나머지에 N을 곱하고 P로 나눈 나머지를 출력한다. 다음에는 이 나머지에 N을 곱한 후 P로 나눈 나머지를 출력한다. 이 과정을 계속 반복해보면 출력되는 에는 반복되는 부분이 있다.

예를 들어서, N = 67, P = 31인 경우를 생각해보자. 처음 출력되는 수는 67이고, 두 번째로 출력되는 수는 67×67 = 4489를 31로 나눈 나머지 25이다. 다음에는 25×67 = 1675를 31로 나눈 나머지 1, 다음에는 1×67 = 67을 31로 나눈 나머지 5가 차례대로 출력된다. 다음에는 5×67 = 335를 31로 나눈 나머지 25가 출력되는데, 이 수는 이미 이전에 출력된 수이다. 이 과정을 그림으로 보이면 다음과 같다.

즉 이 과정을 반복하면, 처음 67을 제외하면 3개의 수 25, 1, 5가 계속 무한히 반복되게 된다. 또 다른 예로, N = 9, P = 3을 가지고 시작하면, 9×9 = 81이고 3으로 나눈 나머지는 0이며, 0×3 = 0이고 3으로 나눈 나머지도 0이기 때문에 처음 9를 제외하면 0이 무한히 반복되게 된다.

N과 P를 입력받아 위와 같이 정의된 연산을 수행하였을 때, 반복되는 부분에 포함된 서로 다른 수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 처음 시작하는 두 자연수 N과 P가 공백을 사이에 두고 주어진다.

출력

첫째 줄에 반복되는 부분에 포함된 서로 다른 수의 개수를 출력한다.

제한

1 ≤ N ≤ 1,000
2 ≤ P ≤ 97

예제 입력 1

67 31

예제 출력 1

예제 입력 2

96 61

예제 출력 2

문제 풀이

문제 해석

문제는 길지만 이 문제에서의 핵심은 "싸이클을 이루는 서로 다른 숫자의 개수는 몇 개인가?"를 묻는 문제이다.라고 해석할 수 있다.

문제 접근 방법

이 문제에서 핵심적인 아이디어는 나머지의 순환을 찾는 것. 시작 수를 N이라고 했을 때, N에 N을 곱하고 P로 나눈 나머지를 구하면 다음 수가 나온다.이 과정을 반복하다보면 언젠가 이전에 구한 나머지와 동일한 나머지가 나올 것이다. 그리고 이후에는 이전에 나온 모든 나머지들이 반복된다.

따라서 나머지가 반복되는 순환 구간을 찾아야 한다. 이를 위해서는 이전에 구한 나머지들을 기록해야 한다. 배열을 사용하여 이전에 나온 나머지들을 기록하고 이전에 나온 나머지와 현재 나온 나머지를 비교하여 순환 구간을 찾을 수 있다.

코드풀이

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

public class Cycle_2526 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // N과 P를 입력받음
        String[] str = br.readLine().split(" ");
        int N = Integer.parseInt(str[0]);
        int P = Integer.parseInt(str[1]);
        // 사이클의 길이를 저장하는 변수 idx, 현재 수를 저장하는 변수 temp, 이미 나온 수를 저장하는 배열 arr을 초기화
        int idx = 0;
        int temp = N;
        int[] arr = new int[P + 1];//나머지의 값이 0~P까지 존재함
        // 사이클을 찾으면 while문을 빠져나가기 위한 변수 isFound를 false로 초기화
        boolean isFound = false;
        // 사이클을 찾을 때까지 반복
        while (!isFound) {
            // 현재 수를 구함
            temp = N * temp % P;
            // 이미 나온 수 중에서 같은 수를 찾으면 사이클의 길이를 출력하고 while문을 빠져나감
            for (int i = 0; i < idx; i++) {
                if (arr[i] == temp) {
                    isFound = true;
                    System.out.print(idx - i);
                    break;
                }
            }
            // 현재 수를 배열에 저장하고 idx를 1 증가시킴
            arr[idx] = temp;
            idx++;
        }
    }
}