Hack!

시간 제한3초메모리 제한2048 MB

요약

해시 테이블의 버킷 수 n(2 이상 1e9 이하)을 알 수 없을 때, 정수 묶음을 질의해 발생한 충돌 횟수로 n을 알아낸다.

난이도: 보통10점 중 7점
유형: 수학, 정수론, 구간
정답자: 아직 제출이 없습니다

문제

It has been an hour into a Codeforces contest, when you notice that another contestant in your room has solved a problem using an unordered_set. Time to hack!

You know that unordered_set uses a hash table with $n$ buckets, which are numbered from $0$ to $n − 1$ . Unfortunately, you do not know the value of $n$ and wish to recover it.

When you insert an integer $x$ into the hash table, it is inserted to the ( $x \bmod n$ )-th bucket. If there are $b$ elements in this bucket prior to the insertion, this will cause $b$ hash collisions to occur.

By giving $k$ distinct integers $x\[0],x\[1], \dots ,x\[k − 1]$ to the interactor, you can find out the total number of hash collisions that had occurred while creating an unordered_set containing the numbers. However, feeding this interactor $k$ integers in one query will incur a cost of $k$ .

For example, if $n = 5$ , feeding the interactor with $x = \[2, 15, 7, 27, 8, 30]$ would cause $4$ collisions in total:

Operation	New collisions	Buckets
initially	$-$	$\[],\[],\[],\[],\[]$
insert $x\[0] = 2$	$0$	$\[],\[],\[2],\[],\[]$
insert $x\[1] = 15$	$0$	$\[15],\[],\[2],\[],\[]$
insert $x\[2] = 7$	$1$	$\[15],\[],\[2, 7],\[],\[]$
insert $x\[3] = 27$	$2$	$\[15],\[],\[2, 7, 27],\[],\[]$
insert $x\[4] = 8$	$0$	$\[15],\[],\[2, 7, 27],\[8],\[]$
insert $x\[5] = 30$	$1$	$\[15, 30],\[],\[2, 7, 27],\[8],\[]$

Note that the interactor creates the hash table by inserting the elements in order into an initially empty unordered_set, and a new empty unordered_set will be created for each query. In other words, all queries are independent.

Your task is to find the number of buckets $n$ using total cost of at most $1\\, 000\\, 000$ .

제한

$1 ≤ t ≤ 10$ , where $t$ is the number of multitests.
$2 ≤ n ≤ 10^9$
$1 ≤ x\[i] ≤ 10^{18}$ for each call to collisions().

예제

이 문제는 공개된 예제가 없습니다.