BOJ 2924 천재

문제 링크입니다.

죄수들의 도전

위 영상을 보고 나면 풀이 이해가 좀더 쉬울 수도 있습니다. 확률에 관한 얘기는 치워두고, 우리는 그냥 순열이 항상 여러 개의 사이클로 이루어져 있다는 것만 알고 가면 됩니다.

문제의 기계가 진행하는 셔플은 순열로 주어진 이 사이클들 위에서 수를 한 칸씩 돌리는 꼴이 됩니다. 그러면 길이가 2인 사이클에서는 셔플 2번마다 사이클 안의 모든 수가 제자리로 돌아오고, 길이가 3인 사이클에서는 셔플 3번마다 제자리로 돌아올 겁니다.

제자리로 되돌리기

그러니 사이클이 실제로 어떻게 연결되어 있는지는 신경쓰지 말고 그냥 각 사이클의 크기만 생각합시다. 분리 집합 등의 자료 구조를 쓰면 간단히 처리할 수 있습니다.

셔플을 여러 번 해서 처음 상태와 일치하게 되려면 모든 사이클에서 그 원소들이 제자리를 찾아가야 합니다. 모든 사이클의 크기의 최소공배수 번마다 이런 현상이 일어나게 됩니다.

결국 문제가 A 이상 B 이하의 수 중 방금 구한 최소공배수의 배수가 몇 개냐를 묻는 문제로 바뀝니다. B 이하의 배수 - (A-1) 이하의 배수로 이를 빠르게 구해줄 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int par[505050];

int f(int x){
	return par[x] < 0 ? x : par[x] = f(par[x]);
}

void u(int x, int y){
	x = f(x); y = f(y);
	if(x == y) return;
	if(par[x] > par[y]) swap(x, y);
	par[x] += par[y]; par[y] = x;
}

ll gcd(ll a, ll b){
	return b?gcd(b,a%b):a;
}
ll lcm(ll a, ll b){
	return a/gcd(a, b)*b;
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	memset(par, -1, sizeof(par));
	int n; ll a, b, c, d; cin >> n >> a >> b >> c >> d;
	for(int i = 1; i <= n; i++){
		int x; cin >> x; u(i, x);
	}
	ll m = 1; for(int i = c+1; i <= n-d; i++) m = lcm(m, -par[f(i)]);
	return !(cout << (b+m-1)/m - (a+m-2)/m);
}