數(shù)論分塊
數(shù)論分塊
定義
用于求解形如
\[\sum_{i=1}^{n}f(i)*g(\left \lfloor \frac{k}{i}\right\rfloor)
\]
的和式，通常被稱為整除分塊，
當(dāng)能用O(1)的時(shí)間求出
\[\sum_{i=1}^{n}f(i)
\]
數(shù)論分塊便能在O(\(\sqrt n\))的時(shí)間內(nèi)求出上式
結(jié)論
\[\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^+,設(shè)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
\]
應(yīng)用
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] 余數(shù)求和
給出正整數(shù) \(n\) 和 \(k\)，請(qǐng)計(jì)算
\[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或大于n
else 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;
}
浙公網(wǎng)安備 33010602011771號(hào)