BOJ 31226 - 고슴도치 그래프 2

문제 링크

• https://www.acmicpc.net/problem/31226
• https://www.acmicpc.net/problem/23049

문제 풀이

임의의 점에서 최대로 이동하면 사이클에 포함된 임의의 노드의 번호를 알 수 있다.
이 번호를 v라고 하자.

개수가 N일때, 2sqrt(N)의 질의로 찾을 순 있는데 900번으로는 어케 찾는거지 ㅜ

24.3. 4
쿼리를 날릴 때 거리가 굉장히 길다.
왜 길까?

정답은 1부터 1,000,000 까지 있다.

1,000,000! 을 k라고 하자.
query(v, k) = v 가 된다.

이것을 응용하는 것 아닐 까?

답이 될 수 있는 정답의 경우의 수를 적절히 압축하여 곱한뒤, 거리 쿼리를 날리고 자기 자신으로 되돌아오는 쿼리를 적절히 빨리 발견하여, 소인수 분해를 통해 빠르게 얻는다… 라고 생각하지만 어케그걸함;

그래봣자 거리쿼리는 10^18이고, 적당히 압축하면 기하급수적으로 커진다.

잘 모르겠다.
목표를 바꾸어서 query(v, x) = v를 뱉는 x들중 하나를 찾는것을 목표로 해보자. x를 찾는다면 30번의 질의 정도로 답을 찾을 수 있다.

이때, x는 한개가 아니다.

1,000,000쿼리를 날리면 1,000,000의 공약수들을 전부 쿼리를 날리는 것과 같다.

목표는 x를 찾는 것이므로, 공약수중 하나가 만약 query(v, x) = v 을 유지한다면, 그 배수인 1,000,000도 query(v, 1000000) = v 이므로 모두 확인한 것이 된다.

이 중첩 현상을 활용하여, 1부터 1,000,000 까지 모두 공약수에 포함되게 하도록 무지무지 크고 복잡한 큰 수 쿼리를 적절하게 날리는 것이 목표가 되겠다.

이 큰수들을 어케 찾아?

24.3.24 solved

제곱근 분할법은 엄청난 힌트가 되었다.

자… 사이클에 속해있는 임의의 점 s에서 시작을 하자.

s로 부터 3칸, s로 부터 10칸 건너 뛰게 되면, 우린 사이클이 3인지 10인지 확인 한 것 뿐만 아니라 사이클이 7인지도 확인 한 것이 된다.

왜냐면 사이클이 7일 경우, s로 부터 3칸 간 것과 10캄 간 것의 도착지점은 같을 것이기 때문이다.

즉, 도착지점이 다른것 또한 하나의 정보가 된다.

이 상태에서 s에서 15칸을 건너 뛴다면,
(15-3) (15-10) 15또한 사이클인지 확인 하게 되는 것이다.

즉 우리는 최대 800번 정도로 질문를 한다면, 800^2 쌍의 수의 차들이 사이클인지 확인한것이 된다는 말이다.

제곱근 분할법… 이것을 수식적으로 왜 항상 자명하게 정답을 얻는지 생각해보자.

A = [1 … sqrt(V)], B = [sqrt(V), 2sqrt(V) … V]
A그룹과 B의 그룹의 수의 차이로 만들 수 있는 수는 [1, 10^6] 전 범위이다. 전 범위가 사이클인지 확인 햇기에 자명하게 정답을 찾아 낼 수 있는 것이다.

하지만 구지 [1, V]의 모든 수가 사이클인지 확인해야 하는 것은 아니다.

3.4 내용과 같이 배수들을 찾아도 괜찮다.
따라서 구간 [1, 500000]의 수들은 [500001, V] 구간에 배수를 갖는다.

따라서 [500001, V] 구간의 수를 전부 확인할 것이다.

그리고 질문 할 수 있는 거리 x = 10^12.4 이므로, 구간 내의 수들을 두개씩 곱해서 25만개의
수로 줄일것이다.

Q = 1000, x < 10^12.4 일 때, 최대 1000000쌍의 수가 생성되기에, 25만개의 수는 잘 어떻게 하면 만들 수 있다.

수의 차이가 일정하게 나는 것을 이용하여, 전 범위를 다 확인 할 수 있다.

수를 작은수부터 순서대로 곱한다음, 2차원상의 매트릭스 형태로 나열하면, 열에 상관없이 수의 차이가 일정해지는 매트릭스 형태의 2차원 배열이 나온다.

Prefix형태로 빼줄 수 있는 수들 500개를 넣어주고, 열에 있는 모든 수 500개씩을 각각 만들 수 있는 기준이 되는 수 500개를 넣어주면,
25만개의 수를 전부 커버할 수 있다.

이것은 고슴도치1의 풀이이다.

Q=800, x < 5e18일 때, 이번엔 모든 홀수만 전부 넣어보자.

구간 [1,999999]의 모든 홀수를 전부 확인 해보자.
홀수의 곱은 홀수이다.
곱셈으로 값을 증가시키며, 홀수가 되는 가장 작은 홀수는 3이다.
그러므로, 구간 [1, 333333]은 [333335, 999999]에 배수를 갖는다.
따라서 [333335, 999999]의 구간의 홀수를 전부 확인해보자.

수가 생각보다 적기때문에 409개의 prefix와 기준이 되는 수 410개를 만들 수 있다.

우리는 존재하는 모든 홀 수를 만들 었기 때문에, 단순히 모든 매트릭스에 2의19승을 곱하는 것 만으로, 모든 짝수도 포함 시킬 수 있다