夢に僕らで帆を張って
来るべき日のために夜を超え

标签 数论分块 下的文章

November 4, 2019

洛谷P3455/POI2007 ZAP-Queries

题意求$$\sum_{i=1}^a \sum_{j=1}^b [\gcd(i,j)=k]$$数据范围:$1 \le d \le a,b \le 50000$题解假设$a\le b$$$ \begin{aligned} \sum_{i=1}^a \sum_{j=1}^b [\gcd(i,j)=k] &= \sum_{i=1}^{\lfloor\frac{a}{k}\rfloor} \s...
September 26, 2019

洛谷P2424 约数和

题意$$f(x)=\sum_{i \mid x} i$$求$$f(x)+ f(x+1)+ \dots +f(y)$$数据范围:$1 \le x<y \le 2 \times 10^9$题解算法:数论分块记$$F(x)=\sum_{i=1}^x f(i)$$可用前缀和,题目所求即为$$F(y)-F(x-1)$$现在计算$F(x)$,对于一个约数$i$,在$[1,x]$中共出现$\lflo...
September 26, 2019

洛谷P2261/CQOI2007 余数求和

题意求$$\sum_{i=1}^nk\%i$$数据范围:$n,k \le 10^9$题解算法:数论分块易知$$k\%i=k- \lfloor \frac{k}{i} \rfloor$$于是$$ \begin{aligned} \sum_{i=1}^n k\%i &= \sum_{i=1}^n k- \lfloor \frac{k}{i} \rfloor \\ &...
September 26, 2019

洛谷P2260/清华集训2012 模积和

题意求$$\sum_{i=1}^n\sum_{j=1}^m (n\%i) \cdot (m\%j),i \neq j$$$\bmod \ 19940417$的值数据范围:$n,m \le 10^9$题解算法:数论分块先不考虑条件$i \neq j$,化简原式$$ \begin{aligned} \sum_{i=1}^n\sum_{j=1}^m (n\%i) \cdot (m\%j) &...