数论分块
定义
用于求解形如
\[\sum_{i=1}^{n}f(i)*g(\left \lfloor \frac{k}{i}\right\rfloor)
\]
的和式，通常被称为整除分块，
当能用O(1)的时间求出
\[\sum_{i=1}^{n}f(i)
\]
数论分块便能在O(\(\sqrt n\))的时间内求出上式
结论
\[\forall k,l\in N^+,(l\leq n)\\\exists r,(1\leq l\leq r \leq n),使得
\left \lfloor \frac{k}{l} \right \rfloor =\left \lfloor \frac{k}{r} \right \rfloor \\
r_{max}=\left \lfloor \frac{k}{\left \lfloor \frac{k}{l} \right \rfloor} \right \rfloor\\
\]
证明
\[\forall x\in N^+,设temp=\left\lfloor\frac{k}{x}\right\rfloor\\
\therefore k=x*temp+r，(0\leq r<x)\\
\therefore k \ge x*temp\\
\therefore x\leq \frac{k}{temp}\\
又\because x\in N^+\\
\therefore x\leq \left\lfloor \frac{k}{temp} \right\rfloor
\]
应用
1.求\(\sum_{i=1}^{n} \left\lfloor \frac{n}{i} \right \rfloor\)
int solve(int n){int res=0;int l=1,r=0;while(l<=n){int temp=n/l;r=n/temp;res+=(r-l+1)*temp;l=r+1;}return res;
}
2.P2261 [CQOI2007] 余数求和
给出正整数 \(n\) 和 \(k\)，请计算
\[G(n,k)=\sum_{i=1}^{n}k\bmod i
\]
分析
\[\because k\bmod i=k-\left\lfloor\frac{k}{i}\right\rfloor*i\\
\therefore \sum_{i=1}^{n}k\bmod i=\sum_{i=1}^{n}k-\left\lfloor\frac{k}{i}\right\rfloor*i\\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =n*k-\sum_{i=1}^{n}\left\lfloor\frac{k}{i}\right\rfloor*i\\
\]
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,k,ans;
ll solve(){ll res=0;ll l=1,r=0;while(l<=n){ll temp=k/l;if(temp==0)r=n;//注意k可能小于n或大于nelse r=min(k/temp,n);ll sum=(r+l)*(r-l+1)/2;res+=sum*temp;l=r+1;}return res;
}
int main(){scanf("%lld%lld",&n,&k);ans=k*n-solve();printf("%lld",ans);return 0;
}