自动搬运

查看原文

来自洛谷，原作者为

	longfei **

搬运于2025-08-24 22:24:22，当前版本为作者最后更新于2020-11-18 00:43:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题解 P6826 【「EZEC-4」月下轻花舞】

@我谔谔 大佬的分$k$大小和前缀和优化思路对我很有启发。但我推式子的过程和大佬有所不同。

推式子思路

注意到 $\left \lceil \log_{i}j \right \rceil \in Z$，所以将 $\left \lceil \log_{i}j \right \rceil$ 以求和号的形式写出来，然后通过交换求和号改变求和顺序，达到去掉大循环的目的。

$$\sum_{i=l}^{r}(i-1)\sum_{j=1}^{n}\left \lceil \log_{i}j \right\rceil = \sum_{i=l}^{r}(i-1)\sum_{j=1}^{n}\sum_{k\geqslant 1}^{}\sum_{i^{k-1}<j}^{}1 $$

式子的核心在于 $i^{k-1}<j$ 。最内层循环为 $i,k$ 时仍需要遍历计算。当最内层循环 $j$ 时，有

$$\sum_{j=1}^{n}\sum_{i^{k-1}<j}^{}1=max(n-i^{k-1},0) $$

于是要求的式子转化为

$$\sum_{i=l}^{r}(i-1)\sum_{k\geqslant 1}max(n-i^{k-1},0) $$

让 $(i-1)max(n-i^{k-1},0)$ 有意义时，$i^{k-1}\leqslant n$，即 $k\leqslant log_{i}n+1$ 。记$t=log_{i}n+1$，有

$$\sum_{i=l}^{r}(i-1)\sum_{k\geqslant 1}max(n-i^{k-1},0)=\sum_{i=l}^{r}\sum_{k\leqslant t}(i-1)(n-i^{k-1}) $$$$=\sum_{i=l}^{r}\sum_{k\leqslant t}(i-1)n -\sum_{i=l}^{r}\sum_{k\leqslant t}(i^{k}- i^{k-1})=\sum_{i=l}^{r}(i-1)nt-\sum_{i=l}^{r}(i^{t}-1) $$$$=\sum_{i=l}^{r}(i-1)nt-\sum_{i=l}^{r}i^{t}+(r-l+1) $$

枚举 $k$ 的值，$k=1,2,3,4$时手算求和公式，$k\geqslant5$时用前缀和数组。处理的区间为$(n,r]$,$(\sqrt[]{n},n]$,$(\sqrt[3]{n},\sqrt[]{n}]$,$(\sqrt[4]{n},\sqrt[3]{n}]$... 最终处理到 $l$ 。

下面附上代码。需要注意诸多细节，在文中说明。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN (1<<16)+5//开到2*10^18的四次根 
#define MAXK 62
#define MAXT 100005//离线，其实可以不用 
#define MOD 998244353
#define re register long long
ll s[MAXN][MAXK];//前缀和数组 
ll l1[MAXT],r1[MAXT],n1[MAXT];//离线取最大的n，其实没必要 
ll base[MAXN];//辅助预处理，记录下标的幂次 
ll fj[MAXK];//记录n^(1/下标) 
ll t,l,r,n,k,maxn;
ll gsc(ll a,ll b){//取模乘法 
	a%=MOD;b%=MOD;
	return (a*b)%MOD;
}
ll dev(ll a,ll b){//取模除法 
	while(a%b!=0)a+=MOD;
	return a/b;
}
void solve(ll l,ll r,ll n){ 
	ll ans=r-l+1;
	memset(fj,0,sizeof(fj));
	for(re i=1;i<=n;i++){
		fj[i]=pow(n,1.00/i);
		if(fj[i]==1)break;//太小的用不到 
	}
	ll inf=l;
	if(r>fj[4]){//手算公式的需要 
		if(r>fj[3]){
			if(r>fj[2]){
				if(r>n){
					inf=n+1;
					inf=max(l,inf);
					if(l<=r){//处理下界 
						ll tmp=dev(gsc(r+inf,r-inf+1),2);
						ans=(ans+dev(gsc(n,gsc(r+inf-2,r-inf+1)),2)-tmp)%MOD;
						while(ans<0)ans+=MOD;
						r=n;//改变上标，大于n的已处理完毕 
					}
				}
				inf=fj[2]+1;
				inf=max(l,inf);
				if(l<=r){
					ll tmp=(dev(gsc(gsc(r,r+1),2*r+1),6)-dev(gsc(gsc(inf-1,inf),2*inf-1),6))%MOD;
					ans=(ans+gsc(n,gsc(r+inf-2,r-inf+1))-tmp)%MOD;
					while(ans<0)ans+=MOD;
					r=fj[2];
				}
			}
			inf=fj[3]+1;
			inf=max(l,inf);
			if(l<=r){
				ll tmp=(dev(gsc(r,gsc(r,gsc(r+1,r+1))),4)-dev(gsc(inf,gsc(inf,gsc(inf-1,inf-1))),4))%MOD;
				ans=(ans+(dev(gsc(n,gsc(r+inf-2,r-inf+1)),2)*3)%MOD-tmp)%MOD;
				while(ans<0)ans+=MOD;
				r=fj[3];
			}
		}
		inf=fj[4]+1;
		inf=max(l,inf);
		if(l<=r){
			ll tmp=dev(gsc(dev(gsc(gsc(r,r+1),2*r+1),6),gsc(gsc(r,r),3)+gsc(3,r)-1),5)-dev(gsc(dev(gsc(gsc(inf-1,inf),2*inf-1),6),gsc(gsc(inf-1,inf-1),3)+gsc(3,inf-1)-1),5);
			ans=(ans+(dev(gsc(n,gsc(r+inf-2,r-inf+1)),2)*4)%MOD-tmp)%MOD;
			while(ans<0)ans+=MOD;
			r=fj[4];
		}
	}
	for(re t=5;t<=log(n)/log(2)+1;t++){
		inf=fj[t]+1;
		inf=max(l,inf);
		if(l>r)break;//处理下界，当当前处理区间下界>=l的时候就退出 
		if(r>fj[t]){
			ll tmp=(s[r][t]-s[inf-1][t]+MOD)%MOD;
			ans=ans+gsc(dev(gsc(n,gsc(r+inf-2,r-inf+1)),2),t)-tmp;
			while(ans<0)ans+=MOD;
			r=fj[t];
		}
	}
	while(ans<0)ans+=MOD;
	printf("%lld\n",ans%MOD);
}
int main(){
	scanf("%lld",&t);
	for(re i=1;i<=t;i++)scanf("%lld%lld%lld",&l1[i],&r1[i],&n1[i]),maxn=max(maxn,n1[i]);
	for(re i=1;i<=(1<<16);i++){
		base[i]=(i*i)%MOD;
		base[i]=(base[i]*base[i])%MOD;
		base[i]*=i;base[i]%=MOD;
	}
	for(re j=5;j<=log(maxn)/log(2)+1;j++){
		for(re i=1;i<=(1<<16);i++){
			s[i][j]=(s[i-1][j]+base[i])%MOD;
			base[i]=(base[i]*i)%MOD;
		}
	}//预处理 
	for(re q=1;q<=t;q++)solve(l1[q],r1[q],n1[q]);
}