A. Gellyfish and Flaming Peony
全体の gcd が $1$ であるとしてよいです．全体の gcd は不変なので，すべて等しくするには $1$ にするしかありません．
最初に $1$ が存在するならば，目標達成まで $1$ 手で $1$ をひとつ増やせるので簡単です．そうでないとき，はじめて $1$ を作るまでのコストを求めます．$x$ を作るまでのコストを $\dp[x]$ として降順に dp すればよいです．
$O(NA\log A)$ で大丈夫でした．
B. Gellyfish and Camellia Japonica
「操作の結果がすべての $i$ で $b_i$ 以上になる」という条件を考えると，「$a_i$ はいくつ以上である」という要素ごとの条件として書けます．この値の下限を逆順に求めます（計算式が作れることがそのまま証明になります）．
この条件を満たす $a$ の中ではもちろん小さいほど「操作の結果がすべての $i$ で $b_i$ に等しくなる」という条件を満たしやすいので，下限をそのまま初期値としてシミュレーションしてチェックします．
$x,y,z$ が異なるわけではないことに注意．
C. Gellyfish and Eternal Violet
確実に単体攻撃が必要な部分を分けて考えます．例えば $(3,3,4,5)$ という列は，「$(3,3,3,3) + 3$」のように考えます．
最小値が $a$ で余ってる量が $b$ という状態を $(a,b)$ と書くと，全体攻撃は $a$ のデクリメント，単体攻撃は $b$ のデクリメントまたは $(a,0)\to (a-1,n-1)$ です．$\dp[t][a][b]$ を，「残り $t$ ターン」「状態 $(a,b)$」のときの成功率として，これを $b<n$ の場合に計算しておきます．
はじめて右側成分が $0$ になるまでは，戦略の分岐は発生しません．この瞬間に注目します．初期状態を $(a,b)$ とすれば，「$b$ 回目の not shine を引いたタイミング」です．
ここまでで shine が出た回数を固定して，その事象の発生確率に，そこからの成功率（上述の dp で計算済）をかけたものを足していけばよいです．発生確率は二項分布ですが，$\log(n!)$ を前計算しておき $\exp$ を使って計算すれば大丈夫です．
D. Gellyfish and Forget-Me-Not
弱い版：https://atcoder.jp/contests/agc045/tasks/agc045_a
でもこれの解説を知らない状態で考え始めた方が良かったかも…（「$0$ にできるかを判定できる方法がある」を一般化しようとして二分探索などを考えると大変になると思います）．
明らかなこととして，「適当な初期値 $x$ からスタートする」「$b_i=0$ である」とできます．
任意の $x$ に対する出力を変えないまま，列 $A, S$ を変形することを考えます．（明らかな例としては，$S=0000$ ならば，列は例の基底を topbit 降順に並べたものに変形できます．そういうのを player 混合でやります）．
結論として，次のような列が存在します．
- $A$ は topbit 降順に並んでいる（特に線形独立）．
- ゲームの出力は，列の左から順に，「$S[i]=1$ ならば $x:=\max(x,x\oplus A[i])$」「$S[i]=0$ ならば $x:=\min(x,x\oplus A[i])$」としたものである（この性質は topbit 降順であることから明らか）
後ろから帰納的に示せます．
列の手前に $a=A_i$ が加えることを考えます．帰納法の仮定から，$a$ に対していま列に書かれている数での基本変形をしても答は変わりません．これで $a=0$ になったら列から削除してもよいです．よって，$a$ はどの $A_i$ とも topbit が異なるとしてよいです．
すると，$A_i$ の topbit が $a$ のそれよりも大きい場合，$A_i$ に対する操作を行うか否かの判断は $a$ に対する操作を行うか否かと独立です．よって，$a$ を topbit 降順になる位置に挿入しなおしてもゲームの出力は変わりません．
E. Gellyfish and Mayflower
まず経路を固定したときの解法の復習です（https://yukicoder.me/problems/no/31）．「効率」最大の $(c_k,w_k)$ を考えます．つまり $w_k/c_k$ が最大であるとします．このとき，他のアイテムは合計で $c_k$ 個以下であるとしてよいです．なぜならば，$c_k$ 個以上あるときにはアイテムのコストを列に並べて累積和を考えることで，ある部分集合のコストの和が $c_k$ の倍数になることが言えるからです．特に，「他のアイテムのコストの和」が $S=c_k\times \max_i(c_i)$ でおさえられます ．よってコスト $S$ 以下の部分を dp すれば解けます．
これを本問に当てはめて，「効率」最大の $k$ を固定して解こうとすると，まだ TLE 計算量になります．実は，クエリに巨大な $r$ しかなかったら，$S$ までの部分の dp を持つ必要はありません．
$0\leq i<c_k$ について，$\dp[i]$ を次のように定義します：「コスト $x$，価値 $y$ の組であって $x\equiv i\pmod{c_k}$ を満たすものに対する $y-x\cdot w_k/c_k$ の最大値」．
この dp の最適解は，$c_k$ 個以下のアイテムで達成できることが上と同じ議論で証明できます．特に dp の最適解を達成する総コストは $S$ 以下の方法があるので，クエリの $r$ が $S$ 以上ならばこの最適解をクエリに適用できます．
結局，本問は次のように解けます：
- $S := \max(C)^2$ とする．
- $r\leq S$ であるようなクエリ：単純な dp で $O((n+m)S+Q)$ 時間で計算可．
- $S<r$ であるようなクエリ：道中で通る効率最大の頂点を固定して $n$ 回解く．それぞれ各頂点で $O(c_k)$ 状態の dp をする．全体で $O(n(Q + (n+m)\max(c)))$ 時間．
あとは選んだ点より効率の良い点を通ったり，選んだ点を通っていないものを ANS に反映したりしないように注意して実装すればよいです．
F2. Gellyfish and Lycoris Radiata (Hard Version)
計算量解析において $N=Q$ とします．クエリ数を $B$ 個ずつのブロックに分けます．
「列のインデックス」「集合のインデックス」という呼び分けをします．はじめ列のインデックス $i$ には集合 $i$ が置かれていて，reverse するたびにこの対応が変わります．
次を保持します．
- [1] 「列のインデックス」に対して「集合のインデックス」がとれるデータ構造．
- 単に区間反転可能な平衡二分木で整数列を管理すればよい．
- [2] 「列のインデックス」に対して「そのブロック内で挿入された数全体」がとれるデータ構造．
- 平衡二分木に bitset<B> を持たせて，区間作用させたり reverse したりする．
- 連長圧縮しておく．つまり最初は「大きさ $N$ のノード」ひとつから始めて，クエリで分割が必要になるたびに分割する．これで平衡二分木のノード数が $O(B)$ になる．
- [3] 「集合のインデックス」に対して，「古いブロック内で挿入された数全体」がとれるデータ構造．
- これはブロックが終了するたびに構築します．
- 各ブロックにおいて，「挿入された数全体」としてありうるパターンが，上述の連長圧縮に対応する $O(B)$ 通りしかないことに注意します．
- これらのパターンにラベルをつけておき，「ブロック・集合のインデックスに対応するラベル」「ブロック・ラベルに対する bitset」を持てばよいです．
- [4] 各ブロックから削除されていない数全体がとれるデータ構造
- ブロックごとに bitset をひとつずつ持つだけです．
クエリ処理方法と計算量（全クエリの和）を確認します．
- クエリ 1：[2] に対して split, apply, merge という要領です．$O(N\log B)$ 回の bitset OR がボトルネックで，計算量 $O(N\log B\times B/w)$ です．
- クエリ 2：[1] は単に $O(N\log N)$ です．[2] に対して上と同様の計算量がかかります．
- クエリ 3：[4] に書き込むだけです．クエリごと $O(1)$ で全体で $O(N)$ 時間です．
- ブロック終了時の処理：ブロックが終了するたびに，[1], [2] の列全体を復元すればよいです．インデックス列の復元に $O(N)$，bitset を $B$ 回保存するところで $O(B^2/w)$ 時間です．このような処理が $O(N/B)$ 回行われるため，$O(N^2/B+NB/w)$ 時間です．
- 求値クエリ：古いブロックについては [3] から，現ブロックからは，[2] から必要な bitset を取ってきます．現ブロックからの取り出しで例の計算量 $O(N\log B\times B/w)$ があります．[4] の bitset との AND をとって _Find_First() により求値します．全部で $O(N^2/w)$ 時間です.
結局，$w<B$ とすると $O((N^2+NB\log B)/w)$ 時間になっていると思います．また [3] で空間 $O(N^2/B)$ がかかることにも注意が必要です．
$N=300000$, $B=4096$ で AC になりました．
