数论分块
数论分块
数论分块就是一个小结论
对于一个常数n，和一个给定的数i(\(i <n\))，能使
\[\lfloor{\frac{n}{i}}\rfloor=\lfloor{\frac{n}{j}}\rfloor
\]
的最大整数j(\(i\le j\le n\))为\(\lfloor{\frac{n}{\lfloor{\frac{n}{i}}\rfloor}}\rfloor{}\)
证明:设\(\lfloor{\frac{n}{i}}\rfloor=x\)
先需要证明\(\lfloor{\frac{n}{j}}\rfloor=x\)
一方面
\[jx=\lfloor{\frac{n}{x}}\rfloor x\le \frac{n}{x}\cdot x=n\\
\]
另一方面
\[\lfloor{\frac{n}{i}}\rfloor=x\Rightarrow \frac{n}{i}< x+1\Rightarrow\frac{n}{x+1} < i \le j\Rightarrow \frac{n}{j} < x+1
\]
因此
\[x\le \frac{n}{j} < x+1 \Rightarrow \lfloor{\frac{n}{j}}\rfloor=x
\]
又因为
\[j=\lfloor{\frac{n}{x}}\rfloor{}>\frac{n}{x}-1 \Rightarrow (j+1)x>(\frac{n}{x}-1+1)x=n\Rightarrow \frac{n}{j+1} < x
\]
因此，当\(j=\lfloor{\frac{n}{\lfloor{\frac{n}{i}}\rfloor}}\rfloor{}+1\)时不满足条件
所以我们得到了\(\lfloor{\frac{n}{i}}\rfloor\)所在块的右端点\(j=\lfloor{\frac{n}{\lfloor{\frac{n}{i}}\rfloor}}\rfloor{}\)
好了，我们已经知道了这个结论了，那我们如何使用呢？
数论分块可以计算一些关于\(\sum_{i=1}^nf(i)\lfloor{\frac{n}{i}}\rfloor\)的一些和式问题
我们只需要将数分成多个块，对于每个块，左端点为l，右端点为\(r=\lfloor{\frac{n}{\lfloor{\frac{n}{i}}\rfloor}}\rfloor{}\)，这样可以减少时间复杂度。
例题
题意：
[CQOI2007]余数求和
题目描述
给出正整数 \(n\) 和 \(k\)，请计算
\[G(n, k) = \sum_{i = 1}^n k \bmod i
\]
思路：
我们可以将\(k \bmod i\)化简一下
\(k \bmod i=k-\lfloor{\frac{k}{i}}\rfloor\)
\[\sum_{i = 1}^n k \bmod i=\sum_{i = 1}^n(k-i\cdot\lfloor{\frac{k}{i}}\rfloor)=n*k-i\cdot\sum_{i = 1}^n\lfloor{\frac{k}{i}}\rfloor
\]
代码
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>
#include<queue>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
int n,m;
ll read()
{
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*f;
}
int main()
{
ll res;
n = read();
ll k = read();
ll l = 1, r;
res = n * k;
while(l <= n)
{
if(l > k)
{
break; //i大于k时直接结束
}
else r = min(k / (k / l),(ll)n);//注意右端点不能超过n！
res -= (r-l+1) * (k / l) *(l+r) / 2;
l = r+1;//更新左端点
}
cout << res;
return 0;
}