[백준] 싸이클

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

2526번: 싸이클

우선 문제부터 간단하게 이야기하면, 

특정한 규칙을 통해 숫자들이 새로 계산됩니다. 이 계산에 의해 숫자들은 순환마디를 가지게 되는데, 이 때, 순환 마디에 포함되는 서로 다른 숫자의 개수를 구해야 하는 문제입니다.

 

<Solution>

차례로 계산을 하는 것은 어렵지 않습니다. 이 때, 순환마디의 길이를 구하는 방식은 크게 두가지를 생각 해 볼 수 있는데,

1. 경로를 찾듯이 구하는 방식 2. 숫자가 몇번째로 등장했는지 기록을 해두는 방식

저의 경우 1번으로 구현을 하였는데, 2번 방법이 더 나은 solution일 것입니다. 예를 들어 3이 4번째에 등장하였고, 8번째에 등장하게 되면, 8과 4의 차이인 4가 반복되는 사이클 내의 원소수일 것이기 때문입니다. 

 

실제 구현은 아래와 같습니다.

#include <iostream>
#include <cstring>
using namespace std;
 
int N, P;
void InputData(){
    cin >> N >> P;
}
int remainder[97];
int count_parent(int k){
    int t = 1;
    int beg = k;
    int index = k;
    while(remainder[index] != beg){
        index = remainder[index];
        t+=1;
    }
 
    return t;
 
}
 
int sol(){
    // initialize remainder array
    memset(remainder, -1, sizeof(remainder));
    int k = N;
    while(1){
        int new_k = (k*N) % P;
         
        if (remainder[new_k] == k){
            // found common part
            return count_parent(new_k);
        }
        else{
            remainder[new_k] = k;
            k = new_k;
        }
 
    }
 
}
 
 
 
int main(){
    int ans = -1;
    InputData();

    ans = sol();
    cout << ans << endl;
    return 0;
}