萌新奇怪方法求助QAQ
查看原帖
萌新奇怪方法求助QAQ
226485
柳苏明楼主2020/8/24 08:19

推得的式子:

t=1min(n,m)(ktk2μ(k)tk)(i=1nt)(i=1mt)\sum_{t=1}^{min\left(n,m\right)}\left(\sum_{k|t}k^2\mu(k)\frac{t}{k}\right)\left(\sum_{i=1}^{\lfloor\frac{n}{t}\rfloor}\right)\left(\sum_{i=1}^{\lfloor\frac{m}{t}\rfloor}\right)

f(n)=i=1ni=n(n+1)2,ν(n)=n2μ(n)f(n)=\sum_{i=1}^ni=\frac{n(n+1)}{2}, \nu(n)=n^2\mu(n)

那么原式化为t=1min(n,m)(νId)(t)f(nt)f(mt)\sum_{t=1}^{min\left(n,m\right)}\left(\nu*\operatorname{Id}\right)(t)f\left(\left\lfloor\frac{n}{t} \right\rfloor\right)f\left(\left\lfloor\frac{m}{t} \right\rfloor\right)

(νId)(t)(\nu*\operatorname{Id})(t)是积性函数,就可以线性筛出来。 (νId)(pα)=ν(1)pα+ν(p)pα+1=pαpα+1=(νId)(pα1)p(\nu*\operatorname{Id})(p^\alpha)=\nu(1)p^\alpha + \nu(p)p^{\alpha+1}=p^\alpha-p^{\alpha+1}=(\nu*\operatorname{Id})(p^{\alpha-1})\cdot p

但只有三十分,请问大佬哪错了啊

代码

inline ll f(const ll i) {
	return (i*(i+1)/2)%mod;
}
ll g[maxn];
void Init(const int &limit) {
	static int prime[maxn],cnt;
	static char not_prime[maxn];
	g[1]=1;
	for(R i(2);i<=limit;i++) {
		if(~not_prime[i]) prime[cnt++]=i,g[i]=(ll)(i-i*i%mod+mod)%mod;
		for(R j(0);j<cnt&&prime[j]<=limit/i;j++) {
			not_prime[i*prime[j]]=0xff;
			if(i%prime[j]==0) {
				g[i*prime[j]]=(ll)(g[i]*prime[j]%mod+mod)%mod;
				break;
			}
			g[i*prime[j]]=(g[i]*g[prime[j]]%mod+mod)%mod;
		}
	}
	for(R i(1);i<=limit;i++) write(g[i]," \n"[i==limit]);
	for(R i(1);i<=limit;i++) g[i]=(g[i]+g[i-1]+mod)%mod;
}

if(n>m) swap(n,m);
	Init(m);
	ll ans=0;
	for(R i(1),j;i<=n;i=j+1) {
		j=min(n/(n/i),m/(m/i));
		(ans+=(ll)(g[j]-g[i-1]+mod)%mod*f(n/i)%mod*f(m/i)%mod+mod)%=mod;
	}
	write(ans,'\n');
2020/8/24 08:19
加载中...