洛谷 P4900 - 食堂(推式子)

洛谷题面传送门

首先推式子:

\[\begin{aligned} ans&=\sum\limits_{i=A}^B\sum\limits_{j=1}^i\{\dfrac{i}{j}\} \end{aligned} \]

考虑差分,设

\[f(n)=\sum\limits_{i=1}^n\sum\limits_{j=1}^i\{\dfrac{i}{j}\} \]

那么

\[ans=f(B)-f(A-1) \]

考虑如何计算 \(f(n)\):

\[\begin{aligned} f(n)&=\sum\limits_{i=1}^n\sum\limits_{j=1}^i\{\dfrac{i}{j}\}\\ &=\sum\limits_{i=1}^n\sum\limits_{j=1}^i\dfrac{i}{j}-\lfloor\dfrac{i}{j}\rfloor\\ &=\sum\limits_{i=1}^ni·\sum\limits_{j=1}^i\dfrac{1}{j}-\sum\limits_{i=1}^n\sum\limits_{j=1}^n\lfloor\dfrac{i}{j}\rfloor\\ \end{aligned} \]

如果设 \(s_i=\sum\limits_{j=1}^i\dfrac{1}{j}\),那么减号前面的东西可写作 \(\sum\limits_{i=1}^ni·s_i\),一遍前缀和求出。下面着重考虑减号右边的东西:

\[\begin{aligned} \sum\limits_{i=1}^n\sum\limits_{j=1}^n\lfloor\dfrac{i}{j}\rfloor \end{aligned} \]

然后就是此题一个比较亮眼的地方了,考虑对 \(\lfloor\dfrac{i}{j}\rfloor\) 进行等价转化,不难发现 \(\lfloor\dfrac{i}{j}\rfloor=\sum\limits_{j\mid k}[k\le i]\),于是乎原式改写为:

\[\sum\limits_{i=1}^n\sum\limits_{j=1}^n\sum\limits_{k\mid j}[k\le i] \]

考虑每个 \(k\) 会对多少对 \((i,j)\) 产生贡献,显然符合条件的 \(i\) 的个数为 \((n+1-i)\),\(j\) 的个数为 \(d(k)\),其中 \(d\) 为约数个数和函数,那么上式可进一步写作:

\[\sum\limits_{k=1}^n(n+1-k)·d(k) \]

维护 \(d(k),k·d(k)\) 的前缀和即可快速计算上式。

如果您比较勤快使用线性筛求解 \(d\) 那么时间复杂度为 \(\mathcal O(n)\),而我比较懒所以直接调和级数枚举,复杂度 \(n\log n\)。

using namespace fastio;
const int MAXN=1e6;
int inv[MAXN+5],s[MAXN+5],ss[MAXN+5],d[MAXN+5],sd[MAXN+5],ssd[MAXN+5];
void init(){
	for(int i=(inv[0]=inv[1]=1)+1;i<=MAXN;i++) inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
	for(int i=1;i<=MAXN;i++) s[i]=(s[i-1]+inv[i])%MOD,ss[i]=(ss[i-1]+1ll*s[i]*i)%MOD;
	for(int i=1;i<=MAXN;i++) for(int j=i;j<=MAXN;j+=i) d[j]++;
	for(int i=1;i<=MAXN;i++) sd[i]=(sd[i-1]+d[i])%MOD,ssd[i]=(ssd[i-1]+1ll*i*d[i])%MOD;
}
int calc(int x){return (ss[x]-(1ll*(x+1)*sd[x]%MOD-ssd[x]+MOD)%MOD+MOD)%MOD;}
int main(){
	init();int qu;read(qu);
	while(qu--){
		int l,r;read(l);read(r);
		printf("%d\n",(calc(r)-calc(l-1)+MOD)%MOD);
	}
	return 0;
}
上一篇:洛谷 P4548 - [CTSC2006]歌唱王国(概率生成函数)


下一篇:拉格朗日插值法