취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 6523번 문제인 요세푸스 한 번 더!이다.
문제는 아래 링크를 확인하자.

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

어떤 사람 x 다음에 걸리는 사람은 어떤 차례인지에 상관없이 이미 a*x^2+b로 정해져있다는 것을 확인하자.

문제 조건에 따라 첫 100만번 연산 이하에서 처음으로 술을 마시는 사람을 찾을 수 있으므로, 해당 사람이 포함된 사이클에 해당하는 사람들만이 술을 마시게 될 것임을 알 수 있다. (그 뒤로 같은 패턴으로만 계속 술을 마시게 된다)

테스트케이스의 수가 적을 것이라 믿고 제출하자(...)

아래는 제출한 소스코드이다.

#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long ll;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	while (N) {
		ll A, B; cin >> A >> B;
		unordered_map<ll,ll> mp;
		ll dist = 1;
		ll x = 0;
		while (mp.find(x) == mp.end()) {
			mp.insert({ x,dist++ });
			x = x * x % N;
			x = (A * x + B) % N;
		}

		cout << N - (dist - mp[x]) << '\n';
		cin >> N;
	}
}