https://www.acmicpc.net/problem/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의 사이즈를 출력하면 사이클을 이루는 수의 개수를 구할 수 있다.
'PS' 카테고리의 다른 글
[BOJ] 1051번 - 숫자 정사각형 (0) | 2017.05.29 |
---|---|
[BOJ] 2512번 - 예산 (0) | 2017.05.29 |
[BOJ]1660번 : 캡틴 이다솜 (0) | 2017.04.26 |
[BOJ]5052번 : 전화번호 목록 (0) | 2017.04.24 |
[BOJ]8983번 : 사냥꾼 (0) | 2017.04.22 |