CF1848

flower1 · 2025-09-18 20:42:58 · 个人记录

CF1848

C

考虑对于每组 (a_i,b_i) 分类讨论，不妨设 a_i \ge b_i。

• 若 a_i \ge 2 \times b_i，可以变为 (a_i - 2k \times b_i,b_i)。
• 若 a_i < b_i，变为 (b_i,b_i-a_i)。

每次至少使 a 减半，时间复杂度 O(n \log n)。

D

容易将以每个位数开始的答案表示为二次函数的形式，求最值即可解决本题。

F

设 f_{i,j} 表示位置 i 经过 j 次操作后的值，容易得到结论 f_{i,{2^k}}=a_i+a_{2^k}。

倍增计算即可。

今天写的有点水不会被发现了吧