[BOJ]2526번 : 싸이클

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

2526번: 싸이클

 

분류 : 없음

 

public class Main {

    public static PrintWriter out;
    public static void main(String[] args) throws IOException {
        MyScanner sc = new MyScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));
        int N = sc.nextInt();
        int P = sc.nextInt();
        Vector<Integer> v = new Vector<Integer>();
        Vector<Integer> rv = new Vector<Integer>();
        int temp = N;
        for(int i=0;i<1000;i++)
        {
            temp = (temp*N)%P;
            
            if(v.contains(temp) && !rv.contains(temp)){
                rv.add(temp);
            }
            v.add(temp);    
        }
        out.println(rv.size());
        out.flush();
    }
}

 

문제는 되게 길지만 결국은 사이클을 이루는 서로 다른 숫자가 몇 개 인가? 하는 문제이다.

 

Vector v 는 계산과정에서 일어나는 모든 수를 집어넣는 벡터, Vector rv는 사이클을 이루는 수를 집어넣는 벡터이다.

 

대략 1000번쯤이면 모든 경우를 해결할수 있지 않을까? 하는 생각에 for문을 1000번까지 돌렸고 , 다행하게도 통과했다.

 

사실 저 부분은 예외 상황이 발생할 수 있는 부분이라 고쳐야 할 것 같긴 하다.

 

그러고 나서 마지막에 rv의 사이즈를 출력하면 사이클을 이루는 수의 개수를 구할 수 있다.