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

再次手把手教你莫反。

题目简介

题目来源：国家集训队 /

评测链接：https://www.luogu.com.cn/problem/P1829
评测链接：https://darkbzoj.cc/problem/2693

形式化题意：求，取模，（不）多测。

数据范围：

非多测

直接推式子（行间渲染较慢，可以等待一会儿）

$\begin{align} ans&= \nonumber \sum_{i=1}^{n}\sum_{j=1}^{m}\operatorname{lcm}(i,j) \\&= \nonumber \sum_{i=1}^{n}\sum_{j=1}^{m}\frac{i\times j}{\gcd(i,j)} \\&=\nonumber \sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d=1}\frac{i\times j}{d}[\gcd(i,j)=d] \\&=\nonumber \sum_{d=1}\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{i\times j}{d}[\gcd(i,j)=d] \\&=\nonumber \sum_{d=1}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}i\times j\times d[\gcd(i,j)=1],i=id,j=jd \\&=\nonumber \sum_{d=1}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}i\times j\times d\sum_{k\mid\gcd(i,j)}\mu(k) \\&=\nonumber \sum_{d=1}\sum_{k=1}d\times\mu(k)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}i\times[k|i]\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}j\times[k|j] \\&=\nonumber \sum_{d=1}^{\min(n,m)}d\sum_{k=1}^{\min(n,m)}\frac{1}{4}k^2\mu(k)\times\left(\left\lfloor\frac{n}{dk}\right\rfloor\times(\lfloor\frac{n}{dk}\rfloor+1) \right)\times\left(\left\lfloor\frac{m}{dk}\right\rfloor\times(\lfloor\frac{m}{dk}\rfloor+1) \right) \\&=\nonumber \sum_{x=1}^{\min(n,m)}\frac{1}{4}x\times\left(\left\lfloor\frac{n}{x}\right\rfloor\times(\lfloor\frac{n}{x}\rfloor+1) \right)\times\left(\left\lfloor\frac{m}{x}\right\rfloor\times(\lfloor\frac{m}{x}\rfloor+1) \right) \sum_{k\mid x}\mu(k)k,x=dk \end{align}$

上面是一大串，如果没有请等待渲染。

我们来分析一下上面一些不太能理解的过程：

对于步，我们用，也就是改为枚举的倍数，使得难以处理的分数被化整。
对于步，因为我们无法处理难以处理的，所以我们转为枚举，然后通过判别函数来判断只有同时满足时才能被计算，也正好将作提前操作。
对于步，考虑消掉的计算，因为已经枚举了，而现在的也是因数，所以我们转为枚举倍数，同步的思想，就可以把消掉，后面就成为了，然后根据公式转为计算，变成了第步的样子。
对于步，用，将枚举改为枚举，而之后我们会枚举，由于枚举了之后也是唯一确定的，所以将枚举提后，单独枚举，用于处理（与无关项）。

对于，我们可以设函数，在线性筛莫比乌斯函数的时候解决，而，考虑使用狄利克雷前缀和预处理。

这样下来，整个式子的计算复杂度被我们控制在了线性，总时间复杂度，可以解决。

AC Code

// ----- Eternally question-----
// Problem: P1829 [国家集训队]Crash的数字表格 / JZPTAB
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1829
// Memory Limit: 500 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-01-04 10:03:04
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e7+10;
const ll Mod=20101009;
int N,M;
inline ll qPow(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1) res=res*a%Mod;
		a=a*a%Mod;b>>=1;
	}
	return res;
}
ll f[MAXN];
int pri[MAXN],Tot,Phi[MAXN],Mu[MAXN];
bool is[MAXN];
inline void sieve(int n)
{
	is[1]=1,Phi[1]=1,Mu[1]=1;
	for(int i=2;i<=n;++i)
	{
		if(!is[i]) pri[++Tot]=i,Phi[i]=i-1,Mu[i]=-1;
		for(int j=1;j<=Tot&&i*pri[j]<=n;++j)
		{
			is[i*pri[j]]=1;
			if(i%pri[j]==0)
			{
				Phi[i*pri[j]]=Phi[i]*pri[j],Mu[i*pri[j]]=0;
				break;
			}
			Phi[i*pri[j]]=Phi[i]*(pri[j]-1),Mu[i*pri[j]]=-Mu[i];
		}
	}
	for(int i=1;i<=n;++i) f[i]=(1ll*i*Mu[i]+Mod)%Mod;
	for(int i=1;i<=Tot;++i)
		for(int j=1;j*pri[i]<=n;++j)
			f[j*pri[i]]=(f[j*pri[i]]+f[j])%Mod;
}
const ll Inv2=(Mod+1)/2;
inline ll calc(int x)
{
	ll res=1ll*x*(N/x)%Mod*((N/x)+1)%Mod*Inv2%Mod*(M/x)%Mod*((M/x)+1)%Mod*Inv2%Mod*f[x]%Mod;
	return res;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,M);
	if(N>M) std::swap(N,M);
	sieve(MAXN-10);
	ll res=0;
	for(int i=1;i<=N;++i) res=(res+calc(i))%Mod;
	write(res);
	return 0;
}
/*

*/

多测（数论分块）

这道题的加强版在上，模数不同（坑），但的范围不变，添加多测，这样的话，用原先的方法会让时间复杂度高达，在计算上花费了大量的时间，导致，所以要进行优化。

我们继续推式子，容易发现是我们熟悉的样子，可以进行数论分块，记对于作前缀和，进行数论分块即可。

坑点在于模数，以及取模溢出。时间复杂度可以压缩到内，虽然看起来很危险但是有时限所以能过。

AC Code

// ----- Eternally question-----
// Problem: P1829 [国家集训队]Crash的数字表格 / JZPTAB
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1829
// Memory Limit: 500 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-01-04 10:03:04
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e7+10;
const ll Mod=20101009;
int N,M;
inline ll qPow(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1) res=res*a%Mod;
		a=a*a%Mod;b>>=1;
	}
	return res;
}
ll f[MAXN];
int pri[MAXN],Tot,Phi[MAXN],Mu[MAXN];
bool is[MAXN];
inline void sieve(int n)
{
	is[1]=1,Phi[1]=1,Mu[1]=1;
	for(int i=2;i<=n;++i)
	{
		if(!is[i]) pri[++Tot]=i,Phi[i]=i-1,Mu[i]=-1;
		for(int j=1;j<=Tot&&i*pri[j]<=n;++j)
		{
			is[i*pri[j]]=1;
			if(i%pri[j]==0)
			{
				Phi[i*pri[j]]=Phi[i]*pri[j],Mu[i*pri[j]]=0;
				break;
			}
			Phi[i*pri[j]]=Phi[i]*(pri[j]-1),Mu[i*pri[j]]=-Mu[i];
		}
	}
	for(int i=1;i<=n;++i) f[i]=(1ll*i*Mu[i]+Mod)%Mod;
	for(int i=1;i<=Tot;++i)
		for(int j=1;j*pri[i]<=n;++j)
			f[j*pri[i]]=(f[j*pri[i]]+f[j])%Mod;
}
const ll Inv2=(Mod+1)/2;
inline ll calc(int x)
{
	ll res=1ll*x*(N/x)%Mod*((N/x)+1)%Mod*Inv2%Mod*(M/x)%Mod*((M/x)+1)%Mod*Inv2%Mod*f[x]%Mod;
	return res;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,M);
	if(N>M) std::swap(N,M);
	sieve(MAXN-10);
	ll res=0;
	for(int i=1;i<=N;++i) res=(res+calc(i))%Mod;
	write(res);
	return 0;
}
/*

*/