自动搬运

查看原文

来自洛谷，原作者为

	Inui_Sana ばか！へんたい！うるさい！⠀

搬运于2025-08-24 23:00:06，当前版本为作者最后更新于2024-09-01 10:03:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

感觉我的做法更魔怔一点。

下取整显然不好搞。于是考虑套路化地变成 $\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{k=0}^{j-1}\frac{ik+x-(ik+x)\bmod j}{j}$。$\frac{ik+x}{j}$ 部分是好处理的，接下来就只考虑 $\frac{(ik+x)\bmod j}{j}$。

注意到 $k$ 取遍 $[0,j-1]$，所以根据 $\gcd(i,j)$ 相同的 $i$，$\sum\limits_{k=0}^{j-1}\frac{(ik+x)\bmod j}{j}$ 是一样的，而这部分可以 $O(1)$ 算。于是先枚举 $j,\gcd(i,j)$ 再推式子。

$$\sum\limits_{i=1}^n\sum\limits_{k=0}^{j-1}(ik+x)\bmod j $$$$=\sum\limits_{l|j}\sum\limits_{i=1}^n[\gcd(i,j)=l]l\sum\limits_{k=0}^{\frac{j}{l}-1}(kl+x)\bmod j $$

然后套路莫反。

$$=\sum\limits_{l|j}\sum\limits_{i=1}^n\sum\limits_{dl|i,dl|j}\mu(d)l\sum\limits_{k=0}^{\frac{j}{l}-1}(kl+x)\bmod j $$

再把 $d$ 往前提。

$$=\sum\limits_{l|j}\sum\limits_{d|\frac{j}{l}}\mu(d)\frac{n}{dl}l\sum\limits_{k=0}^{\frac{j}{l}-1}(kl+x)\bmod j $$

此时就可以枚举 $l$ 再枚举 $d$ 解决了，这个复杂度并没有什么很美丽的表达方式，但是可以写个程序算出计算次数大概是 $5\times 10^7$ 的。稍微卡卡常，比如不用 vector，减少取模次数等，卡着时限过。

code：

int n,m,k,s,mu[N],pm[N],a[N][207],c[N];
bool vis[N];
il int Mod(int x,int y){
	return x+y>=mod?x+y-mod:x+y;
}
il int qpow(int x,int y){
	int ret=1;
	while(y){
		if(y&1){
			ret=1ll*ret*x%mod;
		}
		x=1ll*x*x%mod,y>>=1;
	}
	return ret;
}
void Yorushika(){
	read(n,m);
	double x;scanf("%lf",&x),k=x;
	rep(i,1,m){
		for(int j=i;j<=m;j+=i){
			a[j][++c[j]]=i;
		}
	}
	int ans=0;
	rep(j,1,m){
		int sum=0;
		sum=Mod(sum,1ll*((1ll*(1+n)*n/2)%mod)*((1ll*(j-1)*j/2)%mod)%mod);
		sum=Mod(sum,1ll*n*j%mod*k%mod);
		rep(i,1,c[j]){
			int l=a[j][i];
			ll x=0;
			rep(p,1,c[j/l]){
				int d=a[j/l][p];
				x+=1ll*mu[d]*(n/(d*l))*l;
			}
			int y=k%l;
			y=(1ll*(y+y+(j-l))*(j/l)/2)%mod;
			sum=Mod(sum,mod-1ll*(x%mod+mod)%mod*y%mod);
		}
		ans=Mod(ans,1ll*sum*qpow(j,mod-2)%mod);
	}
	printf("%d\n",ans);
}
signed main(){
	const int mx=5e5;
	mu[1]=1;
	rep(i,2,mx){
		if(!vis[i]){
			pm[++s]=i,mu[i]=-1;
		}
		rep(j,1,s){
			if(pm[j]>mx/i){
				break;
			}
			vis[i*pm[j]]=1;
			if(i%pm[j]==0){
				break;
			}
			mu[i*pm[j]]=-mu[i];
		}
	}
	int t=1;
	//read(t);
	while(t--){
		Yorushika();
	}
}