BZOJ.3994.[SDOI2015]约数个数和(莫比乌斯反演)

$Description$

求$$\sum_{i=1}^n\sum_{j=1}md(ij)$$

$Solution$

有结论：$$d(nm)=\sum_{i|d}\sum_{j|d}[\gcd(i,j)=1]$$

证明可以对质因子单独考虑吧，不想写了，背过就好了。见这：https://blog.csdn.net/PoPoQQQ/article/details/45078079。

\[\begin{aligned}\sum_{i=1}^n\sum_{j=1}^md(ij)&=\sum_{i=1}^n\sum_{j=1}^m\sum_{a|i}\sum_{b|j}[\gcd(a,b)=1]\end{aligned}
\]

转为枚举$a,b$，$$\sum_{i=1}^n\sum_{j=1}md(ij)=\sum_{i=1}^n\sum_{j=1}m\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor[\gcd(i,j)=1]$$

然后反演，设$$F(d)=\sum_{i=1}^n\sum_{j=1}m\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor\left[d\mid(i,j)\right]=\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac md\rfloor}\lfloor\frac{n}{id}\rfloor\lfloor\frac{m}{jd}\rfloor\f(n)=\sum_{i=1}^n\sum_{j=1}m\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor\left[(i,j)=n\right]$$

则$$\begin{aligned}f(1)&=\sum_{d=1}^{{\min(n,m)}\mu(d)F(d)\&=\sum_{d=1}}{\min(n,m)}\mu(d)\sum_{i=1}^{\lfloor\frac nd\rfloor}\lfloor\frac{n}{id}\rfloor\sum_{j=1}^{\lfloor\frac md\rfloor}\lfloor\frac{m}{jd}\rfloor\end{aligned}$$

令$g(n)=\sum_{i=1}\lfloor\frac ni\rfloor$，则$g(n)$可以同样用数论分块$O(n\sqrt n)$的时间预处理。（也可以线性筛出来，不过很麻烦。）

那么$f(1)=\sum_{d=1}^{\min(n,m)}\mu(d)g(\lfloor\frac nd\rfloor)g(\lfloor\frac md\rfloor)$可以$O(\sqrt n)$计算。

终于填了这个近半年前留下的坑了...

//1772kb	6448ms

#include <cstdio>

#include <cctype>

#include <algorithm>

//#define gc() getchar()

#define MAXIN 300000

#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)

const int N=5e4;

int cnt,P[N>>3],mu[N+3];

long long g[N+3];

bool not_P[N+3];

char IN[MAXIN],*SS=IN,*TT=IN;

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

void Init()

{

	mu[1]=1;

	for(int i=2; i<=N; ++i)

	{

		if(!not_P[i]) P[++cnt]=i, mu[i]=-1;

		for(int j=1,v; j<=cnt&&(v=i*P[j])<=N; ++j)

		{

			not_P[v]=1;

			if(i%P[j]) mu[v]=-mu[i];

			else break;//mu[v]=0;

		}

	}

	for(int i=1; i<=N; ++i) mu[i]+=mu[i-1];

	for(int i=1; i<=N; ++i)

	{

		long long ans=0;

		for(int j=1,nxt; j<=i; j=nxt+1)

		{

			nxt=i/(i/j);

			ans+=1ll*(nxt-j+1)*(i/j);

		}

		g[i]=ans;

	}

}

int main()

{

	Init();

	for(int T=read(),n,m; T--; )

	{

		n=read(),m=read();

		long long ans=0;

		for(int i=1,nxt,lim=std::min(n,m); i<=lim; i=nxt+1)

		{

			nxt=std::min(n/(n/i),m/(m/i));

			ans+=1ll*(mu[nxt]-mu[i-1])*g[n/i]*g[m/i];

		}

		printf("%lld\n",ans);

	}

	return 0;

}

巴特西

BZOJ.3994.[SDOI2015]约数个数和(莫比乌斯反演)

\(Description\)

\(Solution\)

最新文章

热门文章