爆搜
先来考虑固定 kkk 时怎么做。设 bi=∑j=1iajb_i=\sum_{j=1}^i a_jbi=∑j=1iaj, 发现
∀1≤i≤n,k∣ai\forall 1 \leq i \leq n, k | a_i∀1≤i≤n,k∣ai
可以转化为
∀1≤i≤n,k∣bi\forall 1 \leq i \leq n, k | b_i∀1≤i≤n,k∣bi
同时可以发现:
那么当固定 kkk 时, 答案:
因此,我们只需 O(bn)O(\sqrt{b_n})O(bn) 地枚举 kkk,取 min\minmin 即可
使用您的 Hydro 通用账户