线性预处理整除分块
线性预处理整除分块
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132596085
有时候要求前 个：
暴力整除分块是 的，但可以线性预处理
首先我们让 取遍 0 到正无穷，考虑差分。
思考 变成 ，哪些 会发生变化。只有 的因数，所以差分出来其实就是 的 因数个数 。这个可以线性筛 预处理。
然后再做个前缀和就还原成原数组了。
可于杜教筛的分类讨论。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2022-01-18
【SSOJ 2913: 「一本通 6.4 例 3」Sumdiv】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15817137.html 题目 原题来自：Romania OI 2002 求 ABA^BAB 的所有约数之和 mod 9901\bmod 9901mod9901。 思路 首先按照算术基本定理: A=p1k1×p2k2×⋯×pnkn\Large A=p_1^{k_1}\times p_2^{k_2}\times\cdots\times p_n^{k_n} A=p1k1×p2k2×⋯×pnkn 所以： AB=p1k1×B×p2k2×B×...
2021-11-24
【NOIP2021 报数】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15600119.html 题目链接 想着T2，T3的题解都写了，就补一下T1的吧。 典型的筛法。 假如一个数含有7，则把它的倍数全筛走。 这里可以加一个小优化，假如这个数已经被筛过，就不需要再筛它的倍数了。 最后再倒着预处理每个数的下一个没被筛的是什么。 如果不预处理，不断6999999就可以卡死你。 Code 12345678910111213141516171819202122232425262728293031323334353637383...
2021-11-14
线性筛欧拉筛的应用
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15551853.html 线性筛/欧拉筛的应用 线性求 ipi^pip 若 iii 是质数，则我们用快速幂求 ipi^pip。 若 iii 不是质数，则在欧拉筛里，必然可以用最小的质数 p1p_1p1，使得 p1×j=ip_1\times j=ip1×j=i，于是我们就可以得到结论： ip=(p1×j)p=p1p×jpi^p=(p_1\times j)^p=p_1^p\times j^p ip=(p1×j)p=p1p×jp 线性求欧拉...
2023-09-03
线性求逆元
线性求逆元 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132650059 先暴力求出 1n!\frac 1 {n!}n!1 往回推出 1i!\frac 1 {i!}i!1 1i=(i−1)!i!\Large \frac 1 i=\frac{(i-1)!}{i!}i1=i!(i−1)!
2022-01-16
【P3538 [POI2012]OKR-A Horrible Poem】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15810272.html 题目 原题来自：POI 2012 给出一个由小写英文字母组成的字符串 S，再给出 q 个询问，要求回答 S 某个子串的最短循环节。 如果字符串 B 是字符串 A 的循环节，那么 A 可以由 B 重复若干次得到。 思路 首先，我们如果有三点： 一个字符串的循环节必然是字符串长度的约数 循环节的倍数如果长度还是字符串长度的约数，那么他也是循环节 如果一个长度 iii 是字符串循环节长度，那么 [l,r−i][l, r-i]...
2021-12-14
二项式定理
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15689044.html (a+b)n=∑k=0nCnkakbn−k\Large(a+b)^n=\sum_{k=0}^n C_n^ka^kb^{n-k} (a+b)n=k=0∑nCnkakbn−k 在化简一些式子时有用 因此，2n2^n2n （也就是当 a=b=1a=b=1a=b=1 ）时也可以表示为： 2n=∑k=0nCnkakbn−k\Large2^n=\sum_{k=0}^n C_n^ka^kb^{n-k} 2n=k=0∑nCnka...