首页
关于
笔记
文章
友链

Solution -「LOCAL 28731」Rainyrabbit 爱求和

cirnovsky /

§ Description

Link.

Rainyrabbit⁡\operatorname{Rainyrabbit} 是一个数学极好的萌妹子，近期他发现了一个可爱的函数：

f(n,m,k)=∑d=1ndk⌊nlcm⁡(d,m)⌋f(n,m,k)=\sum_{d=1}^n d^k\lfloor\dfrac{n}{\operatorname{lcm}(d,m)}\rfloor

其中 lcm⁡(d,m)\operatorname{lcm}(d,m) 表示 dd 和 mm 的最小公倍数。

她觉得只算这一个函数太单调了于是想要对这个函数求和，给出 a,b,ca,b,c，求：

∑i=1a∑j=1b∑k=0cf(i,j,k)\sum_{i=1}^a\sum_{j=1}^b\sum_{k=0}^cf(i,j,k)

同时 I.w.rabbit⁡\operatorname{I.w.rabbit} 固定 cc 的值不变，给出 TT 组 a,ba,b，请回答此时式子对 998244353998244353 取模后的值。

算是概括过了额。

§ Solution

先看 ff 怎么把那个烦死的整除去掉。

f(n,m,k)=∑d=1ndk⌊nlcm(d,m)⌋=∑d=1ndk⌊ndmgcd⁡(d,m)⌋=∑d=1ndk⌊ndmgcd⁡(d,m)⌋\begin{aligned} f(n,m,k)&=\sum_{d=1}^{n}d^{k}\lfloor\frac{n}{\text{lcm}(d,m)}\rfloor \\ &=\sum_{d=1}^{n}d^{k}\lfloor\frac{\frac{n}{d}}{\frac{m}{\gcd(d,m)}}\rfloor \\ &=\sum_{d=1}^{n}d^{k}\lfloor\frac{\frac{n}{d}}{\frac{m}{\gcd(d,m)}}\rfloor \\ \end{aligned}

来看 ⌊ndmgcd⁡(d,m)⌋\lfloor\frac{\frac{n}{d}}{\frac{m}{\gcd(d,m)}}\rfloor，因为 ⌊ab⌋=∑i=1a[b∣i]\lfloor\frac{a}{b}\rfloor=\sum_{i=1}^{a}[b|i]，所以 ⌊ndmgcd⁡(d,m)⌋=∑i=1⌊nd⌋[mgcd⁡(d,m)∣i]=∑i=1⌊nd⌋[m∣id]\lfloor\frac{\frac{n}{d}}{\frac{m}{\gcd(d,m)}}\rfloor=\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}[\frac{m}{\gcd(d,m)}|i]=\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}[m|id]。所以

f(n,m,k)=∑d=1ndk⌊ndmgcd⁡(d,m)⌋=∑d=1ndk∑i=1⌊nd⌋[m∣id]=∑m∣in∑d∣idk=∑m∣inσk(i)\begin{aligned} f(n,m,k)&=\sum_{d=1}^{n}d^{k}\lfloor\frac{\frac{n}{d}}{\frac{m}{\gcd(d,m)}}\rfloor \\ &=\sum_{d=1}^{n}d^{k}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}[m|id] \\ &=\sum_{m|i}^{n}\sum_{d|i}d^{k} \\ &=\sum_{m|i}^{n}\sigma_{k}(i) \\ \end{aligned}

然后代回原式。

∑i=1a∑j=1b∑k=0c∑j∣diσk(d)=∑k=0c∑d=1aσk(d)(a−d+1)∑j=1b[j∣d]\begin{aligned} \sum_{i=1}^{a}\sum_{j=1}^{b}\sum_{k=0}^{c}\sum_{j|d}^{i}\sigma_{k}(d)&=\sum_{k=0}^{c}\sum_{d=1}^{a}\sigma_{k}(d)(a-d+1)\sum_{j=1}^{b}[j|d] \\ \end{aligned}

考虑如何计算 ∑k=0cσk(d)\sum_{k=0}^{c}\sigma_{k}(d)。把函数又拆回去：

∑k=0cσk(d)=∑w∣d∑k=0cwk=∑w∣dwc+1−1w−1\begin{aligned} \sum_{k=0}^{c}\sigma_{k}(d)&=\sum_{w|d}\sum_{k=0}^{c}w^{k}=\sum_{w|d}\frac{w^{c+1}-1}{w-1} \end{aligned}

最后一步是等比数列求和，然后你就可以调和级数预处理了。具体来说就是线筛的时候筛一下 wc+1w^{c+1}，这东西是个完全积性函数，你乱筛就行了。

设这玩意儿为 s(d)=∑w∣dwc+1−1w−1s(d)=\sum_{w|d}\frac{w^{c+1}-1}{w-1}，原式改写为：

∑d=1as(d)(a−d+1)∑j=1b[j∣d]\sum_{d=1}^{a}s(d)(a-d+1)\sum_{j=1}^{b}[j|d] \\

然后后面那个 sigma 你也可以反过来直接调和级数。还有就是 b>ab>a 的时候没有贡献，所以可以取个 min⁡\min，这样能多几分。

来看看怎么屮多测。

和 数表 那道题一样，我们把询问离线下来，以 bb 为关键字排序后树状数组。

把中间那个系数拆出来，变成：

∑d=1a(a+1)s(d)−d×s(d)∑j=1b[j∣d]\sum_{d=1}^{a}(a+1)s(d)-d\times s(d)\sum_{j=1}^{b}[j|d] \\

前面那个好说，直接来；后面就在树状数组修改时乘上系数即可。

综上，维护两个树状数组即可。

#include<cstdio>
#include<algorithm>
using namespace std;
void read(long long &x)
{
	x=0;
	char c=getchar();
	while(c<'0'||c>'9')	c=getchar();
	while(c>='0'&&c<='9')
	{
		x=(x<<3)+(x<<1)+(c^'0');
		c=getchar();
	}
}
void write(long long x)
{
	if(x>9)	write(x/10);
	putchar((x%10)^'0');
}
const long long mod=998244353;
struct node
{
	long long a,b,ID;
}nodes[200010];
struct fenwick
{
	#define lowbit(x) ((x)&-(x))
	long long fen[1000010],mx;
	void ins(long long x,long long y)
	{
		while(x<=mx)
		{
			fen[x]=(fen[x]+y)%mod;
			x+=lowbit(x);
		}
	}
	long long find(long long x)
	{
		long long res=0;
		while(x)
		{
			res=(res+fen[x])%mod;
			x^=lowbit(x);
		}
		return res;
	}
}onefe,anofe;
long long t,a,b,c,tag[1000010],prime[1000010],cnt,fu[1000010],exfu[1000010],power[1000010],cur=1,mx,ans[200010];
bool cmp(node one,node ano)
{
	return one.b<ano.b;
}
long long cqpow(long long bas,long long fur)
{
	long long res=1;
	while(fur)
	{
		if(fur&1)	res=res*bas%mod;
		bas=bas*bas%mod;
		fur>>=1;
	}
	return res;
}
void search(long long x)
{
	tag[1]=power[1]=1;
	for(long long i=2;i<=x;++i)
	{
		if(!tag[i])
		{
			prime[++cnt]=i;
			power[i]=cqpow(i,c+1);
		}
		for(long long j=1;j<=cnt&&prime[j]*i<=x;++j)
		{
			tag[prime[j]*i]=1;
			power[prime[j]*i]=power[prime[j]]*power[i]%mod;
			if(i%prime[j]==0)	break;
		}
	}
	fu[1]=(c%mod+1)%mod;
	for(long long i=2;i<=x;++i)	fu[i]=((power[i]-1+mod)%mod)*cqpow(i-1,mod-2)%mod;
	for(long long i=1;i<=x;++i)
	{
		for(long long j=i;j<=x;j+=i)	exfu[j]=(exfu[j]+fu[i])%mod;
	}
}
int main()
{
	read(t);
	read(c);
	search(1000000);
	for(long long i=1;i<=t;++i)
	{
		read(nodes[i].a);
		read(nodes[i].b);
		nodes[i].ID=i;
		nodes[i].b=min(nodes[i].a,nodes[i].b);
		mx=max(mx,nodes[i].a);
	}
	sort(nodes+1,nodes+t+1,cmp);
	onefe.mx=anofe.mx=mx;
	for(long long i=1;i<=mx&&cur<=t;++i)
	{
		for(long long j=i;j<=mx;j+=i)
		{
			onefe.ins(j,exfu[j]);
			anofe.ins(j,exfu[j]*j%mod);
		}
		while(i==nodes[cur].b)
		{
			ans[nodes[cur].ID]=((onefe.find(nodes[cur].a)*(nodes[cur].a+1))%mod-anofe.find(nodes[cur].a)+mod)%mod;
			cur++;
		}
	}
	for(long long i=1;i<=t;++i)
	{
		write(ans[i]);
		putchar('\n');
	}
	return 0;
}