P1829 [国家集训队]Crash的数字表格 / JZPTAB 题解

Kaitlyn ·

更新时间:2024-09-21

· 837 次阅读

博客园同步

原题链接

简要题意：

求

∑i=1n∑j=1mlcm⁡(i,j)\sum_{i=1}^n \sum_{j=1}^m \operatorname{lcm}(i,j)i=1∑nj=1∑mlcm(i,j)

一言不合就推式子。

∑i=1n∑j=1mlcm⁡(i,j)\sum_{i=1}^n \sum_{j=1}^m \operatorname{lcm}(i,j)i=1∑nj=1∑mlcm(i,j)

=∑i=1n∑j=1mijgcd⁡(i,j) = \sum_{i=1}^n \sum_{j=1}^m \frac{ij}{\gcd(i,j)}=i=1∑nj=1∑mgcd(i,j)ij

=∑d=1min⁡(n,m)1d∑i=1m∑j=1nij[gcd⁡(i,j)==d] = \sum_{d=1}^{\min(n,m)} \frac{1}{d} \sum_{i=1}^m \sum_{j=1}^n ij [\gcd(i,j)==d]=d=1∑min(n,m)d1i=1∑mj=1∑nij[gcd(i,j)==d]

=∑d=1min⁡(n,m)1d∑i=1⌊nd⌋∑j=1⌊md⌋ijd2[gcd⁡(i,j)==1] = \sum_{d=1}^{\min(n,m)} \frac{1}{d} \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} ijd^2 [\gcd(i,j)==1]=d=1∑min(n,m)d1i=1∑⌊dn⌋j=1∑⌊dm⌋ijd2[gcd(i,j)==1]

=∑d=1min⁡(n,m)d∑i=1⌊nd⌋∑j=1⌊md⌋[gcd⁡(i,j)==1] = \sum_{d=1}^{\min(n,m)} d \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} [\gcd(i,j)==1]=d=1∑min(n,m)di=1∑⌊dn⌋j=1∑⌊dm⌋[gcd(i,j)==1]

=∑d=1min⁡(n,m)d∑i=1⌊nd⌋∑j=1⌊md⌋ij∑x∣gcd⁡(i,j)μx = \sum_{d=1}^{\min(n,m)} d \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} ij \sum_{x | \gcd(i,j)} \mu_x=d=1∑min(n,m)di=1∑⌊dn⌋j=1∑⌊dm⌋ijx∣gcd(i,j)∑μx

=∑d=1min⁡(n,m)d∑x=1min⁡(⌊nd⌋,⌊md⌋)x2μxs⌊ndx⌋s⌊mdx⌋ = \sum_{d=1}^{\min(n,m)} d \sum_{x=1}^{\min(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)} x^2 \mu_x s_{\lfloor \frac{n}{dx} \rfloor} s_{\lfloor \frac{m}{dx} \rfloor}=d=1∑min(n,m)dx=1∑min(⌊dn⌋,⌊dm⌋)x2μxs⌊dxn⌋s⌊dxm⌋

其中

sx=∑i=1xi=x×(x+1)2s_x = \sum_{i=1}^x i = \frac{x \times (x+1)}{2}sx=i=1∑xi=2x×(x+1)

回到原式：

=∑T=1ns⌊nT⌋s⌊mT⌋(T∑d∣TdμT) = \sum_{T=1}^n s_{\lfloor \frac{n}{T} \rfloor} s_{\lfloor \frac{m}{T} \rfloor} \big(T \sum_{d|T} d \mu_T \big)=T=1∑ns⌊Tn⌋s⌊Tm⌋(Td∣T∑dμT)

括号内的东西我们预处理，括号外面的直接 整除分块。（实际上没有这个必要了）

那么如何预处理呢？单独搞出这个式子。

T∑d∣TdμTT \sum_{d|T} d \mu_TTd∣T∑dμT

TμT∑d∣TdT \mu_T \sum_{d|T} dTμTd∣T∑d

咦？是不是很熟悉？ TμTT \mu_TTμT 我们直接预处理就可以了。考虑，令：

fi=∑d∣idf_i = \sum_{d|i} dfi=d∣i∑d

（其实 fif_ifi 就是 iii 的因数之和）

那么可得：

fi×j=fi×fj([gcd⁡(i,j)]==1)f_{i \times j} = f_i \times f_j \big([\gcd(i,j)]==1 \big)fi×j=fi×fj([gcd(i,j)]==1)

即 fff 为 积性函数。

所以用线性筛预处理即可。

时间复杂度：O(n)O(n)O(n).

实际得分：100pts100pts100pts.

#pragma GCC optimize(2)
#include
using namespace std;
typedef long long ll;
const int N=1e7+1;
const ll MOD=20101009;
inline int read(){char ch=getchar(); int f=1;while(ch'9') {if(ch=='-') f=-f; ch=getchar();}
	int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
int prime[N],mu[N],n,m;
int cnt=0; bool h[N];
ll ans=0;
inline void Euler(int n) {
	mu[1]=1; for(register int i=2;i<=n;i++) {
		if(!h[i]) mu[i]=MOD-i+1,prime[++cnt]=i;
		for(register int j=1;j<=cnt && i*prime[j]<=n;j++) {
			h[i*prime[j]]=1;
			if(i%prime[j]==0) {mu[i*prime[j]]=mu[i];break;}
			mu[i*prime[j]]=(1ll*mu[i]*mu[prime[j]])%MOD;
		}
	} for(register int i=1;i<=n;i++) mu[i]=1ll*mu[i]*i%MOD;
	for(register int i=1;i>1)%MOD;} //求 s
int main() {
	Euler(N-1);
	n=read(),m=read();
	if(n>m) swap(n,m);
	for(int l=1;l<=n;) {
		int r=min(n/(n/l),m/(m/l));
		ans=(ans+1ll*(mu[r]-mu[l-1]+MOD)*Sieve(n/l)%MOD*Sieve(m/l)%MOD)%MOD;
		l=r+1; //整除分块
	} printf("%lld\n",ans);
	return 0;
}