质数与数差类题目：ZR2639三色堇

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132325425

Trick 1

题目要求维护差的平方和。但发现差得数量很少。

对于维护和差有关的东西（比如此题中的 $\sum(a_i-a_{i-1})^2$ ），如果差的数量很少，可以直接维护差的数量 $f_i$ ，最后可以计算为 $i^2\times f_i$

Trick 2

考虑数之间的差怎么转移。之前我们的 $f_i$ 是按 $p_0$ 划分，现在考虑加入 $p$ ，我们就以 $p$ 划分。那么只需考虑上面的段会不会被切断即可，切断的贡献部分和优化一下。

对于多质数类题目，如果是统计值域上的问题，可以考虑通过不同质数来划分。关键点在于对于 $i\bmod p$ ，会取遍 $0\sim p-1$