이면 간선이 없는 에서도 조건을 만족하므로 정답은 이다. 이하에서는 인 경우를 생각하자. 이고 이라고 하자. 정점을 번호 순서대로 크기 인 블록으로 나누면 각 블록이 정확히 하나의 연결 요소가 된다. 마지막 블록의 정점 수가 더 적어도 마찬가지이다. 따라서 연결 요소의 개수는
이다. 이 값은 가 부터 까지 변하는 동안 일정하다. 그러므로 가장 작은 는 의 거듭제곱 중 하나이다. 부터 시작하여
가 될 때까지 를 두 배로 늘리면 된다. 처음으로 조건을 만족하는 가 정답이다. 천장 함수는 양의 정수 , 에 대한 등식 를 이용하여 계산할 수 있다. 시간 복잡도는 이고, 추가 공간 복잡도는 이다.
증명
이라 하고, 번째 블록을 을 만족하는 정점 들의 집합으로 정의하자. 실제로 존재하는 정점만 포함하므로 마지막 블록은 개보다 적은 정점을 포함할 수도 있다. 서로 다른 블록에 있는 두 정점의 번호는 번째 이상의 비트 중 적어도 하나가 다르다. 따라서 두 번호의 XOR은 이상이며 보다 크다. 서로 다른 블록을 잇는 간선은 없다. 한 블록의 첫 정점 번호를 이라고 하자. 이 블록의 임의의 정점 에서, 번호의 번째부터 번째 비트 중 켜져 있는 비트를 하나씩 끄면 에 도달한다. 번째 비트를 끄는 한 단계에서 두 정점 번호의 XOR은 이므로 두 정점 사이에 간선이 있다. 이 과정에서는 상위 비트가 변하지 않으므로 계속 같은 블록에 머문다. 또한 번호가 감소하기만 하므로 모든 중간 정점의 번호는 이상이고 처음의 이하이다. 따라서 마지막 블록이 완전히 채워져 있지 않아도 모든 중간 정점이 존재한다. 블록의 모든 정점이 와 연결되므로 각 블록은 하나의 연결 요소이다. 블록의 개수는 이므로 연결 요소의 개수도 이다. 이 개수는 인 동안 변하지 않으므로 해당 구간에서는 가장 작은 값 만 확인하면 된다. 이면 은 조건을 만족하지 않는다. 를 순서대로 확인하면 조건을 만족할 수 있는 모든 구간의 시작점을 작은 순서대로 확인하게 된다. 따라서 처음으로 조건을 만족하는 값이 정답이다.
Solution written by GPT6
