(C++) - 백준(BOJ) 2526번 : 싸이클

www.acmicpc.net/problem/2526

2526번: 싸이클

간단한 구현문제였습니다.

 

풀이방법

 1. n은 최대 1000, p가 97까지이므로 나머지를 적용했을 때 96이하의 수가 나오므로 배열 1000개로 어떤 숫자가 몇 번째 항인지를 구할 수 있습니다. 해당 변수는 vector자료형 nums로 선언합니다.

 

 2. while loop를 돌면서 이미 셌던 수가 나올때까지 다음을 수행합니다.

   2-1. 수 ne는 n으로 시작합니다. 그러면서 수 ne가 수열에서 몇 번째 항인지를 저장해줍니다. 항은 cnt로 표시됩니다.

   2-2. ne = ne * n % p로 갱신합니다.

 

 3. 답을 출력합니다. nums[ne]는 ne의 몇 번쨰 항인지를 나타내므로 전체항이 저장된 cnt에서 nums[ne]를 빼준것이 반복되는 구간입니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
int n,p,ne,cnt=1;
vector <int> nums(1001); 

int main(){
    cin >> n >> p;
    ne = n;
    while(!nums[ne]){
        nums[ne] = cnt++;
        ne = ne * n % p;
    }
    cout << cnt - nums[ne] << '\n';
}