어떤 사람들은 와 같이 결국 하나의 원소로 생성된다는 것을 직관을 통해 알아내어 풀 것이다. 본문에서 이 추측이 왜 올바른지 설명하고, 문제의 풀이에 대해 간략하게 정리하였다. 쓸데없이 복잡해졌다고 생각하므로 더 좋은 증명에 대한 의견을 얻을 수 있으면 하는 마음이다.
추측이 옳은 이유
을 만족하는 정수 는 벡터 공간 의 원소로 볼 수 있다. 이러한 대응은 를 이진법으로 전개하여, 번째 자리를 번째 에 대응시킴으로써 가능하고, 역으로 대응시키는 것도 가능하다. 앞으로의 풀이에서 맥락에 따라 는 벡터 공간 혹은 0보다 크거나 같고 보다 작은 정수들로 이루어진 집합으로 해석된다. 는 위의 덧셈, 즉 정수의 xor 연산을 나타낸다. 를 0을 포함하지 않는 의 부분집합이라고 하면, 조건 1에 의해 조건을 만족하는 는 의 부분공간이다.
문제의 조건을 모두 만족하는 집합 에 대해, 이는 어떤 에 대해 으로 표현될 수 있다. 0이 아닌 원소 에 대해, 의 원소를 정수로써 다루었을 때 , 꼴로 표현되는 모든 원소를 의 shift라고 하자. 를 의 모든 shift로 이루어진 집합이라고 하자. 모든 에 대해, 는 어떤 에 대해 로 생성되는 부분 공간 과 같음을 보일 것이다.
에 포함된 가장 작은 양의 정수를 라고 하고, 를 이진 전개하였을 때의 길이를 라고 하자. 가 짝수이면 조건 3에 의해 가 에 포함되고 이는 의 최소성에 모순이므로 는 홀수이다. 는 선형독립이고, 각 원소는 꼴로 나타남을 관찰하자. 에서 는 기저를 이룬다. 은 벡터 공간으로써의 성질을 고려하면 조건 1을 만족함을 알 수 있다.
조건 3: 이면 이다. 어떤 가 유일하게 존재하여
이다. 이때 좌변은 짝수이므로 이다. 따라서 이다. 이므로 이다.
조건 2: 이고 이라고 하자. 어떤 가 유일하게 존재하여
이다. 이때 의 이진 전개에서 자리 수는 0이고, 따라서 이다. 이고, 이므로 이다.
따라서 이다. 한편, 조건 2, 3에 의해 이고, 조건 1에 의해 는 에 대해 닫혀있다. 따라서 는 선형공간이고, 을 포함한다. 따라서 이다.
이라고 하자. 를 으로 생성되는 부분공간이라고 하면, 이는 이진 전개의 길이가 이하인 모든 수들의 집합과 같다. 따라서 이다. 한편 임의로 주어진 에 대해
을 만족하는 를 항상 찾을 수 있다. 따라서
는 완전열이고, 계수-퇴화차수 정리로부터 이다. 한편 의 크기는 이므로, 이고 이다. 따라서
를 얻는다.
풀이
두 양의 정수 에 대해, 를 에 포함된 가장 작은 정수로 정의하자. 이는 다항식에서의 유클리드 호제법을 응용하여 계산할 수 있고, 가 작다면 빠르게 계산된다. 를 정의로부터 알 수 있는데, 문제에서 모든 이 보다 작으므로 풀이에서 사용할 계산은 모두 상수 시간 복잡도로 계산할 수 있다. 양의 정수 에 대해,
를 관찰하자. 첫 번째 등식은 이므로 성립한다. 주어진 나무에서 적당히 뿌리를 정하고, 각 정점에 대해 번째 조상과 그 정점에서 번째 조상까지 가는 경로에 놓인 모든 를 하는 sparse table을 만들 수 있다. 특히 는 와 같이 idempotent한 성질 덕분에 sparse table을 만들 때 뿌리에서 더 올라가려고 하는 것에 대해 어떤 예외 처리를 하지 않아도 되어 간편하다. 만들어낸 sparse table을 이용하여 각 쿼리에 대해 lca를 이용해 최단경로를 찾아내면서 그 경로의 모든 를 한 값을 의 시간 복잡도로 구할 수 있다.
