由于最近在学习莫比乌斯反演,发现整除分块这个东西几乎是很是必要的,由于是真的好用,能够把一些须要\(O(n)\)的枚举优化到$O(\sqrt n)html
什么式子能够用整除分块呢?通常是这样
\[\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor\]
咱们发现(打表或者是本身yy),对于一段连续的区间,\(\lfloor\frac{n}{i}\rfloor\)的值是不变的,那么对于这一段区间,咱们就能够跳过,\(O(1)\)计算出这一段区间的值c++
既然是分块,那么一块的边界是什么呢?
首先,明确一点,首端点l是枚举出来的,而末端点是\(n/(n/l)\)(感性理解一下)
而据dalao分析,时间复杂度是\(O(\sqrt n)\),有了这个范围,咱们就能够分块了函数
inline void init (int ans=0) {
for(int l=1,r,len;l<=n;l=r+1) {
r=n/(n/l),len=r-l+1;
ans+=len*(n/l);
}
} 不少时候,整除分块是配合其余一些函数来用的,such as \(\mu\),\(\phi\)...
当咱们的区间跳跃的时候,函数值也会跳跃,因此就要记得乘上这一段区间的函数值,这个时候就须要前缀和优化了
听dalao说,有些恶心的题目会卡线性筛(T飞),这个时候就须要杜教筛,你问我杜教筛是什么?问得好,我也不知道(逃~是真的,之后有时间再补吧)学习
放几道整除分块的例题
[AHOI2005]约数研究
[CQOI2007]余数求和
洛谷P3935 Calculating
第一题没什么思路,直接预处理,在这里放一下代码优化
#include<bits/stdc++.h>
#define il inline
#define rg register
#define lol long long
#define Min(a,b) (a)<(b)?(a):(b)
#define Max(a,b) (a)?(b)?(a):(b)
using namespace std;
void in(int &ans) {
ans=0; char i=getchar();
while(i<'0' || i>'9') i=getchar();
while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+i-'0',i=getchar();
}
int main()
{
int n,ans=0; in(n);
for(rg int l=1,r,len;l<=n;l=r+1) {
r=n/(n/l),len=r-l+1;
ans+=n/l*len;
}
printf("%d\n",ans);
} 第二题也是转换一下题目要求的东西
\[a\mod b= a-\lfloor\frac{a}{b}\rfloor\times b\]
而后套一下等比数列求和就能够了
注意一下边界spa
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define il inline
#define rg register
#define lol long long
#define Min(a,b) (a)<(b)?(a):(b)
#define Max(a,b) (a)?(b)?(a):(b)
using namespace std;
void in(lol &ans) {
ans=0; char i=getchar();
while(i<'0' || i>'9') i=getchar();
while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+i-'0',i=getchar();
}
int main()
{
lol n,m;in(n),in(m); lol ans=n*m;
for(rg lol l=1,r,len;l<=n;l=r+1) {
if(m/l!=0) r=Min(m/(m/l),n);
else r=n; len=(r-l+1);
ans-=(m/l)*len*(l+r)/2;
}
printf("%lld\n",ans);
} 第三题题解code
下面是配合莫比乌斯反演的题
[POI2007]ZAP-Queries 题解1
[SDOI2015]约数个数和 题解2
YY的GCD 题解3htm