给一个数列,求其前缀min等于数列末端元素的和.
首先跑一下pr发现后面是一个质数.两个数都是1e15级别的数,显然不是暴力能搞定的,因为质数保证了在[0,p]内所有值都会出现一次.
对于这种题一般有两种解法:求到一半,发现函数再后面几乎无影响了,然后直接交算了一半的解.
或者中途换算法.
发现在2e10左右,欧拉币大小已经收敛到了2e5,此时可以使用exgcd求解值对应的步数,具体地,求解 $ax+by=1$ 然后乘值c,对步数排个序,算一下前缀min.
总复杂度 $O(2e10+2e5\log2e5)$ .