CF1618E Singers' Tour

有 $n$ 个城镇顺时针排列成一个环，城镇编号为 $1$ 到 $n$。第 $i$ 个城镇住着一位歌手，他的曲库初始时长为 $a_i$ 分钟，$i \in [1, n]$。 每位歌手从自己所在的城镇出发，顺时针依次访问所有 $n$ 个城镇，在每个城镇举办一场演唱会。在每个城镇，歌手都会受到启发，创作出一首时长为 $a_i$ 分钟的新歌，并将其加入曲库，以便在接下来的城市演唱。 因此，对于第 $i$ 位歌手，在第 $i$ 个城镇的演唱会时长为 $a_i$ 分钟，在第 $(i+1)$ 个城镇时长为 $2 \cdot a_i$ 分钟，……，在第 $((i+k) \bmod n + 1)$ 个城镇时长为 $(k+2) \cdot a_i$ 分钟，……，在第 $((i+n-2) \bmod n + 1)$ 个城镇时长为 $n \cdot a_i$ 分钟。 现给定一个数组 $b$，其中 $b_i$ 表示第 $i$ 个城镇所有演唱会的总时长。请你还原出任意一个满足条件的正整数序列 $a$，或者判断是否不存在这样的序列。

第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。接下来是 $t$ 组测试数据。 每组测试数据包含两行。第一行包含一个整数 $n$（$1 \le n \le 4 \times 10^4$），表示城市数量。第二行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$1 \le b_i \le 10^9$），表示第 $i$ 个城市所有演唱会的总时长。 所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出如下内容： 如果不存在满足条件的序列 $a$，输出 NO。否则，第一行输出 YES，第二行输出 $n$ 个整数 $a_1, a_2, \dots, a_n$，其中 $a_i$（$1 \le a_i \le 10^9$）为第 $i$ 位歌手初始曲库时长。如果有多组解，输出任意一组即可。

以样例的第 $1$ 组为例： 1. 第 $1$ 位歌手在第 $1$ 个城市演唱会时长为 $3$ 分钟，在第 $2$ 个城市为 $6$ 分钟，在第 $3$ 个城市为 $9$ 分钟； 2. 第 $2$ 位歌手在第 $1$ 个城市演唱会时长为 $3$ 分钟，在第 $2$ 个城市为 $1$ 分钟，在第 $3$ 个城市为 $2$ 分钟； 3. 第 $3$ 位歌手在第 $1$ 个城市演唱会时长为 $6$ 分钟，在第 $2$ 个城市为 $9$ 分钟，在第 $3$ 个城市为 $3$ 分钟。 由 ChatGPT 4.1 翻译