백준 6523번 조세퍼스 한 번 더!

문제 링크입니다: https://www.acmicpc.net/problem/6523

조세퍼스 문제를 변형시킨 문제였습니다.

알고리즘은 아래와 같습니다.

1. 두 번 걸린 사람이 나올 때까지 while문을 돌리고 map에 이 사람이 몇 번째인지 표시해줍니다.

2. 1번을 마치면 정답을 알 수 있는데 N명 중에 cnt명이 지목을 당했었고 그 중 drinker[cur] 즉, 제일 처음으로 술을 마시게 된 사람이 몇 번째로 지목을 당했었는지 알기 때문에 답은 N - cnt + drinker[cur]입니다.

#include <iostream>

#include <map>

using namespace std;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

       

        while (1)

        {

                 long long N, a, b;

                 cin >> N >> a >> b;

 

                 if (N == 0)

                         break;

 

                 map<int, int> drinker;

                 int cur = 0;

                 int cnt = 0;

                 while (1)

                 {

                         cur = ((a*cur%N) * cur%N + b) % N;

                         if (drinker.find(cur) != drinker.end())

                                 break;

 

                         drinker[cur] = cnt++;

                 }

 

                 cout << N - (cnt - drinker[cur]) << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~