(백준/C++) 2526 사이클

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

문제 해석(시간 제한 1초)

예를 들어서, 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이 무한히 반복되게 된다.

단순히 생각해보면, 숫자가 나오면 최대 크기의 숫자만큼의 count 배열을 만들어 나온 숫자의 개수를 체크해주면 될 것 같습니다. 그렇게 되면 count가 2인 숫자들은 반복되었다는 것을 쉽게 확인 할 수 있습니다.

시간복잡도로 따지면 최대 O(N)의 나올 수 있습니다. 즉, O(1000)이므로 1초 안에 통과 가능합니다.

#include <iostream>

using namespace std;

int n, p;
int arrCnt[98], cnt = 0;

int main() {
    cin >> n >> p;
    int temp = n;
    while(true) {
    	temp = (temp * n) % p;
		if(arrCnt[temp] == 2) break;
		arrCnt[temp] += 1;
    }
	for(int i = 0; i < p; i++) {
		if(arrCnt[i] == 2) cnt++;
	}
    cout << cnt << endl;
    return 0;
}