luoguP3327 [SDOI2015]约数个数和

题意

首先有个结论：

\(d(i,j)=\sum\limits_{x|i}\sum\limits_{y|j}[gcd(x,y)=1]\)

证明：

假设\(i=p_1^{a_1}*p_2^{a_2}*...*p_k^{a_k},j=p_1^{b_1}*p_2^{b_2}*...*p_k^{b_k}\)，则\(i*j=p_1^{a_1+b_1}*p_2^{a_2+b_2}*...*p_k^{a_k+b_k}\)

考虑第\(i\)个质因子\(p_i\)，如果\(x,y\)互质，则\(x,y\)只能有一个有\(p_i\)，x有是\(a_i\)种，\(y\)有是\(b_i\)种，都没有是1种，总共\((a_i+b_i+1)\)种，与约数个数和公式中相符。

于是式子变为：

\(\sum\limits_{i=1}^n\sum\limits_{j=1}^{m}\sum\limits_{x|i}\sum\limits_{y|j}[\gcd(x,y)=1]\)

改为枚举\(x,y\)：

\(\sum\limits_{x=1}^{n}\sum\limits_{y=1}^m[\gcd(x,y)=1]*\frac{n}{x}*\frac{m}{y}\)

设\(f(x)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^m\frac{n}{i}*\frac{m}{j}*[\gcd(i,j)=x],F(x)=\sum\limits_{n|d}f(d)\)

则：

\(F(x)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\frac{n}{i}*\frac{m}{j}*[x|\gcd(i,j)]\)

提出\(x\)：

\(F(x)=\sum\limits_{i=1}^{\frac{n}{x}}\sum\limits_{j=1}^{\frac{m}{x}}\frac{n}{i*x}*\frac{m}{j*x}*[1|\gcd(i,j)]\)

即：

\(F(x)=\sum\limits_{i=1}^{\frac{n}{x}}\sum\limits_{j=1}^{\frac{m}{x}}\frac{n}{i*x}*\frac{m}{j*x}\)

莫比乌斯反演：

\(f(x)=\sum\limits_{x|d}\mu(\frac{d}{x})F(x)\)

\(ans=f(1)=\sum\limits_{1|d}\mu(\frac{d}{1})F(d)\)

\(=\sum\limits_{d=1}^{min(n,m)}\mu(d)\sum\limits_{i=1}^{\frac{n}{d}}\sum\limits_{j=1}^{\frac{m}{d}}\frac{n}{i*d}*\frac{m}{j*d}\)

预处理\(g(x)=\sum\limits_{i=1}^{x}\frac{x}{i}\)，并求出莫比乌斯函数的前缀和\(sum_i\)，后面那一部分显然可以除法分块。

code:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=5*1e4+10;

int T,n,m;

int mu[maxn],sum[maxn];

ll g[maxn];

bool vis[maxn];

vector<int>prime;

inline void shai(int n)

{

	vis[1]=1;mu[1]=1;

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

	{

		if(!vis[i])prime.push_back(i),mu[i]=-1;

		for(unsigned int j=0;j<prime.size()&&i*prime[j]<=n;j++)

		{

			vis[i*prime[j]]=1;

			if(i%prime[j]==0)break;

			mu[i*prime[j]]=-mu[i];

		}

	}

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

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

		for(int l=1,r;l<=i;l=r+1)

			r=i/(i/l),g[i]+=1ll*(r-l+1)*(i/l);

}

inline ll solve(int n,int m)

{

	ll res=0;

	for(int l=1,r;l<=min(n,m);l=r+1)

	{

		r=min(n/(n/l),m/(m/l));

		res+=1ll*(sum[r]-sum[l-1])*g[n/l]*g[m/l];

	}

	return res;

}

int main()

{

	shai(50000);

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d%d",&n,&m);

		printf("%lld\n",solve(n,m));

	}

	return 0;

}

巴特西

luoguP3327 [SDOI2015]约数个数和

题意

最新文章

热门文章