약수1 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번째 후속노드를 가리키는 그래프는 쪼개진다. 그 외의 경우 사이클의 순서는 바뀔 수 있지만 구성요소는 바뀌지 않는다. 사이클마다 약수번째 후속노드를 가리키는 그래프가 inf.. 2020. 3. 24. 이전 1 다음