P15552 [CCPC 2025 Harbin Site] k-Subset Sum Greatest Common Divisor Problem

Consider an infinite multiset $S$, whose elements include $a_1, a_2, \cdots, a_n$, and each type of element appears infinitely many times. Based on this, we define a function $f(k)$ as follows: for every subset $S'$ of $S$ with size exactly $k$, compute the sum of elements in $S'$. Take the greatest common divisor of all such sums, and use it as the value of $f(k)$. Formally, $$ f(k) = \gcd_{S' \subseteq S, |S'| = k} \left( \sum_{x \in S'} x \right) $$ For example, for $a = [3, 6]$, we have $$ f(2) = \gcd(3 + 3, 3 + 6, 6 + 6) = 3 $$ Now please find the maximum value of $f(k)$, and the smallest $k$ that achieves this maximum. In particular, if the maximum value does not exist, report ``infinite``.

This problem contains multiple test cases. The first line contains an integer $T$ ($1 \le T \le 4 \times 10^5$), representing the number of test cases. Then each test case is given as follows: The first line contains an integer $n$ ($1 \le n \le 10^5$), representing the number of distinct values in $S$. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^{18}$), representing the elements in $S$. It is guaranteed that the sum of $n$ over all test cases does not exceed $4 \times 10^5$.

For each test case, if $f(k)$ has a maximum value, output one line with two integers: the maximum value of $f(k)$, and the smallest $k$ that achieves this maximum. Otherwise output ``infinite`` (without quotes).

For the first test case in Sample 1, you can find that no matter what $k$ is, $f(k)=3$. For the second test case in Sample 1, we have $f(k)=2k$, so $f$ grows without bound and the maximum value does not exist. Translated by ChatGPT 5