[백준] 2526 싸이클

 

숫자 사이의 사이클을 찾는 쉬운 문제다!

스택 개념을 사용하면 금방 풀 수 있다

 

진짜 스택을 써도 괜찮고 배열에 넣어도 괜찮다

 

먼저 숫자를 계산하고 check배열을 통해 표시해준다

그리고 스택에 계속 넣어준다

 

그러다가 만약 이미 나온 숫자가 또 나온다면

스택에서 그 숫자부터 top까지의 수가 답이된다!

 

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;
bool arr[1000010];
int n, k;
 
int getnum(int num) {
    return((n*num) % k);
}
int main() {
    scanf(" %d %d", &n, &k);
    stack<int> st;
 
    int num = n;
    while (!arr[num]) {
        st.push(num);
        arr[num] = 1;
        num = getnum(num);
    }
    int ans = 0;
    while (st.top() != num) {
        ans += 1; st.pop();
    }
    printf("%d\n", ans + 1);
}