ACM-ICPC-OJ训练营

问题 B: Problem M. Windblume Festival

时间限制: 1 Sec 内存限制: 128 MB
提交: 0 解决: 1
[提交][状态][讨论版][命题人:]

题目描述

The Windblume Festival in Mondstadt is coming! People are preparing windblumes for Barbatos and for

those they love and adore. The Windblume Festival is also an opportunity to improve the relationships

people have.

During the festival, a famous game will be played every year, invented by Jean, the Acting Grand Master

of the Knights of Favonius. In the game, n players numbered from 1 to n stand in a circle, each holding

an integer with them. Each turn, one player will be removed. The game will end when there is only one

player left.

For each turn, let k be the number of players remaining and ai be the integer player i holds. Two adjacent

players, x and (x mod k + 1) are selected and player (x mod k + 1) is removed from the game. Player x’s

integer will then change from ax to (ax − ax mod k+1). Player y in this turn will become player (y − 1) in

the next turn for all x < y ≤ k, though the integer they hold will not change.

Jean wants to know the maximum possible integer held by the last remaining player in the game by

selecting the players in each round optimally

There are multiple test cases. The fifirst line of the input contains one integer T indicating the number of

test cases. For each test case:

The fifirst line contains one integer n (1 ≤ n ≤ 1e6 ) indicating the initial number of players.

The next line contains n integers ai (−1e9 ≤ ai ≤ 1e9 ) where ai is the integer held by player i at the

beginning.

It is guaranteed that the sum of n of all test cases will not exceed 1e6.

For each test case output one line containing one integer indicating the maximum possible integer.

2
4
1 -3  2 -4
11
91 66 73 71 32 83 72 79 84  33 93

10
713

For the fifirst sample test case follow the strategy shown below, where the underlined integers are the

integers held by the players selected in each turn.

{1, −3, 2, −4} (select x = 4) → {−3, 2, −5} (select x = 2) → {−3, 7} (select x = 2) → {10}