Educational 84 div2 D - Infinite Path (약수, 수론, 후속노드그래프)

https://codeforces.com/contest/1327/problem/D

약수를 모두 구하는 건 O(루트n), 전처리 후 O(n^(1/3))

소인수분해는 필요 없다.

 

<문제설명>

사이클 덩어리들이 주어진다. 사이클에 포함된 u,v에 대해 u->v면 v->u경로가 반드시 있다.(주어진 p 배열이 순열이므로)

번호마다 색이 주어진다.

 

사이클에서 k번째 후속노드를 가리키는 그래프가 모두 같은 색을 이룰 때 infinite path를 이룬다고 하자.

 

infinite path가 존재하기 위한 k의 최소값을 구해라.

 

 

<풀이>

사이클의 크기의 1이아닌 약수 k번째 후속노드를 가리키는 그래프는 쪼개진다. 그 외의 경우 사이클의 순서는 바뀔 수 있지만 구성요소는 바뀌지 않는다.

 

사이클마다 약수번째 후속노드를 가리키는 그래프가 infinite path를 이루는지 검사해주면 된다.

 

<코드>

int n, p[MAX],ans;
vector<int> clr;
vector<bool> vst;

void init() {
	clr.clear();
	vst.clear();
	clr.resize(n+1);
	vst.resize(n + 1);
	ans = n; 
}

bool pos(vector<int> a, int t) { //a사이클에 간격t 모든 요소 색이 같으면 true
	for (int i = 0; i < t; i++) {
		bool flag = true;

		int x = a[i];
		for (int j = 1; i+j*t < a.size(); j++) {
			int y = a[i+j*t];
			if (clr[x] != clr[y]) {
				flag = false;
			}
		}

		if (flag) return true;
	}
	
	return false;
}

int main() {
	FAST;
	int tt; cin >> tt;
	while (tt--) {
		cin >> n;
		init();
		for (int i = 1; i <= n; i++) cin >> p[i];
		for (int i = 1; i <= n; i++) cin >> clr[i];

		vector<vector<int>> chain;
		for (int i = 1; i <= n; i++) if(!vst[i]) {
			int temp = p[i];
			vector<int> vv; vv.push_back(i);
			vst[i] = true;
			while (temp != i) {
				vv.push_back(temp);
				vst[temp] = true;
				temp = p[temp];
			}
			chain.push_back(vv);
		}

		for (auto ch : chain) {
			for (int i = 1; i * i <= ch.size(); i++) {
				if (ch.size() % i == 0) {
					if (pos(ch, i)) ans = min(ans, i);
					if(i*i!=ch.size() && pos(ch,ch.size()/i)) ans = min(ans, (int)ch.size()/i);
				}
			}
		}

		cout << ans << '\n';
	}
}

 

 

<생각>

약수를 미리 전처리해두면 약수의 개수만큼 도는 반복문에 O(n^(1/3))의 시간이 걸리는 것으로 기대할 수 있다.

 

굳이 전처리를 안해도 루트n만큼의 시간으로 충분히 돌아간다.