P14199 [ICPC 2024 Hangzhou R] Make It Divisible

Given a sequence $a_1, a_2, \cdots, a_n$ of length $n$ containing positive integers, we say an interval $[l, r]$ ($1 \le l \le r \le n$) is a $\textit{divisible interval}$ if there exists an integer $d$ such that $l \le d \le r$ and for all $l \le i \le r$, $a_i$ is divisible by $a_d$. We say the whole sequence is a $\textit{divisible sequence}$ if for all $1 \le l \le r \le n$, $[l, r]$ is a divisible interval. Given another sequence $b_1, b_2, \cdots, b_n$ of length $n$ and an integer $k$, find all integers $x$ such that $1 \le x \le k$ and the sequence $b_1 + x, b_2 + x, \cdots, b_n + x$ is a divisible sequence. As the number of such integers might be large, you just need to output the number and the sum of all such integers.

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 500$) indicating the number of test cases. For each test case: The first line contains two integers $n$ and $k$ ($1 \le n \le 5 \times 10^4$, $1 \le k \le 10^9$). The second line contains $n$ integers $b_1, b_2, \cdots, b_n$ ($1 \le b_i \le 10^9$). It's guaranteed that the sum of $n$ of all test cases does not exceed $5 \times 10^4$.

For each test case output one line containing two integers separated by a space, where the first integer is the number of valid $x$, and the second integer is the sum of all valid $x$.

For the first sample test case, $x = 1$, $x = 2$ and $x = 5$ are valid. For the third sample test case, all $1 \le x \le 100$ are valid.