백준 2526번: 싸이클

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

1. 문제

두 자연수 N과 P를 가지고 다음 과정을 거쳐서 나오는 숫자들을 차례대로 출력해보자. 처음 출력하는 숫자는 N이고, 두 번째 이후 출력하는 숫자들은 N을 곱하고 P로 나눈 나머지를 구하는 과정을 반복하여 구한다. 즉, 먼저 N에 N을 곱하고, 이 수를 P로 나눈 나머지를 두 번째에 출력한다. 다음에는 이 나머지에 N을 곱하고 P로 나눈 나머지를 출력한다. 다음에는 이 나머지에 N을 곱한 후 P로 나눈 나머지를 출력한다. 

이 과정을 계속 반복해보면 출력되는 숫자들에는 반복되는 부분이 있다. 예를 들어서, 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가 출력되는데, 이 수는 이미 이전에 출력된 수이다. 이 과정을 그림으로 보이면 다음과 같다.

2. 알고리즘

[Figure 1]

1차원 배열을 선언하여 현재 계산할 값을 대입 한다.

싸이클에 입력받은 n과 p 의 값으로 다음 값을 계산 한다.

예제에서는 N = 67, P = 31 임으로 계산 공식에 의해 다음 수는 25가 된다.

[Figure 2]

1차원 배열에 다음 인덱스에 현재 계산할 값을 대입 한다.

figure 1 에 동작을 반복 한다.

[Figure 3]

1차원 배열에 다음 인덱스에 현재 계산 할 값을 대입 한다.

figure 3 도 figure2 처럼 figure 1 에 동작을 반복 한다.

[Figure 4]

figure1 동작을 반복 한다.

[Figure 5]

위 동작을 반복 하다 보면 순환되는 영역을 확인 할 수 있다.

계산된 값을 배열에 대입 하면서 순환되는지 확인 하기 위해 검사코드를 추가 해야 한다.

        for (int i = 0; i < sol; i++) {
            // 현재 계산 된 값이 순환 되는지 확인 한다.
            if (arr[i] == cand) {
                // 순환이 된다면 현재 index로 부터 sol(계산된 수를 저장한 배열의 인덱스) 차이 값을 출력 한다.
                cout << sol - i << "\n";
                return 0;
            }
        }    

3. 코드

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <cstring>
 
#define MAX_SIZE 100
#define INF 0x7fffffff
 
using namespace std;
 
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int reverse(int x) {
    int rev = 0;
    while(x != 0){
        rev = rev*10 + x%10;
        x = x/10;
    }
    return rev;
}
 
int main() {
 
    std::ios::sync_with_stdio(false); cin.tie(0);
 
    int n, p; cin >> n >> p;
    int arr[100] ={0,};
    int sol = 0;
    arr[sol++] = n;
    
    int cand = n;
    while (true)
    {
        cand = (cand * n) % p;
        for (int i = 0; i < sol; i++) {
            // 현재 계산 된 값이 순환 되는지 확인 한다.
            if (arr[i] == cand) {
                // 순환이 된다면 현재 index로 부터 sol(계산된 수를 저장한 배열의 인덱스) 차이 값을 출력 한다.
                cout << sol - i << "\n";
                return 0;
            }
        }
        
        arr[sol++] = cand;
    }
    return 0;
}