SWEA 11316. 주기 찾기

슈도랜덤 제너레이터(Pseudorandom Generator) 가 아래와 같을 때 이 슈도랜덤 제너레이터의 주기를 구하는 문제이다.

-  A0 = s
-  Ai = (pㆍAi-1 + q) mod m (i≥1)

s,p,q,m(0 ≤ s,p,q < m ≤ 10^6)

 

배열을 사용해서 시작 값부터 index 저장 후 공식에 따라 숫자를 만들어 나간다. 그러면서 배열에 해당 위치의 값이 0이 아니면 반복되므로 현재 index - 배열 값 이 주기가 된다.

Arrays.fill(visited, 0, m, 0);
            
int num = s;
int index = 1;
visited[num] = index++;
            
while (true) {
    num = (int) (((long) p * num + q) % m);
                
    if (visited[num] > 0) {
        sb.append(index - visited[num]).append('\n');
        break;
    }
    visited[num] = index++;
}

 

 

결과 코드는 다음과 같다.

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

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        int[] visited = new int[1000001];
        
        StringBuilder sb = new StringBuilder();
        for (int tc = 1; tc <= T; tc++) {
            sb.append('#').append(tc).append(' ');
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken()), p = Integer.parseInt(st.nextToken()), q = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            Arrays.fill(visited, 0, m, 0);
            
            int num = s;
            int index = 1;
            visited[num] = index++;
            
            while (true) {
                num = (int) (((long) p * num + q) % m);
                
                if (visited[num] > 0) {
                    sb.append(index - visited[num]).append('\n');
                    break;
                }
                visited[num] = index++;
            }
        }
        
        br.close();
        System.out.print(sb);
    }
}