Storm-数论分块

Superiority · 2025-02-05 11:59:40 · 算法·理论

Math-数论分块

• 数论分块又称整数分块，只要体现于思想，很少以模板本身考。

整数分块顾名思义，将整数如分块思想一样分成很多块，但如何分了？其实很显然，我们设此整数为 x，则可以分为 \frac{x}{1},\frac{x}{2},\frac{x}{3}...\frac{x}{x-1}这些部分。但其时间复杂都并无改变。举几个例子可以发现一些微妙的规律，越往后面相同的数且连续的越来越多，此时我们尝试将相同的数分为一块。我们可以定义一个 l 为此时分块左端点，这时有小孩哥就要问了这玩意儿咋分块啊！即使以相同为分块的基本规则但同上所述时间复杂度无任何改变。其实很简单的一个式子即可我们定此时的值为 k ，那如何找到分块右端点 r 呢？ 此时用 x/k 就可以完美解决了！思考一下why?此时的值为k，由于前文提到过将有相同 k 的分在一起为一个块，所以如果此时除以x的数为awa则有显而易见x/k=awa,则x/k一定是符合条件且最大的位置则为右端点r，此时既然已经将一个区块干掉，则往下一个块搜！那如果求权值呢？这时自己慢慢推式子吧！毕竟有一块相等的特性...

for(int l=1;l<=x;l++){
    int k=x/l,r=x/k;
    //Code value add 加权
    l=r;
}