CVBB ACM Team

给出一个长度为$n$的序列，问多少次前缀和操作后序列最大值可以超过$k$，保证序列至少有两个数为正。$(2 \le n \le 2 \times 10^5, 1 \le k \le 10^{18})$

由F题可知，前缀和操作的增长速度是$O(x^{n-1})$的，在$k=10^{18}$的数据范围下，只有$n=2,3$时暴力模拟复杂度过高，其它情况都可以直接暴力模拟。$n=2$时就是一直加一个数，可以直接算；$n=3$时就是一直加一个数和一个等差数列求和，解二次方程或二分都可以。（注意去掉所有前导$0$剩下的位数才是真正的$n$，因为前面的$0$无论多少次操作都不会变）

给出一个长度为$n$的序列$a_i$，求$$\sum_{\gcd(a_{i_{1}},a_{i_{1}},\cdots,a_{i_{k}}) \ne 1}k \cdot \gcd(a_{i_{1}},a_{i_{1}},\cdots,a_{i_{k}}) \pmod{10^9+7}$$其中$1 \le k \le n, i_1<i_2< \cdots < i_k$。$(n \le 2 \times 10^5, a_i \le 10^6)$

本题是Coprime Subsequences的升级版。