Readme

1590.Make-Sum-Divisible-by-P

假设整个数组的和除以P的余数是r0. 题目要求subarray的剩余数字和除以P于0，那么就意味着这个subarray sum除以P的余数就是r0. 于是本题就转化成了求最短的subarray，满足和是r0.

假设我们探索这样的subarray，令其右边界是j，那么左边界i可以取在哪里呢？我们可以利用前缀和的思想。如果presum[j]%P==r，那么我们必然要求presum[i]%P==r-r0（当然如果r-r0<0，那么我们就要补上一个周期变成r-r0+P）. 所以我们转化为了求与j最接近的索引i，满足presum[i]%P==r-r0。 显然，我们在遍历之前的presum的时候，可以每次都求一下它除以P的余数，然后存下余数->索引的映射关系。此时，我们就可以直接调用Map[r-r0]得到该余数对应的、最近的presum的索引值。

本题要注意，计算totalSum和preSum的过程中，都有可能会溢出。但事实上，所有的操作都和取余有关，所以我们只需要每一步求和都取余就行了。