SDOI2015 约数个数和

wjh15101051's space

卧薪尝胆，厚积薄发。

SDOI2015 约数个数和

Date: Wed Jul 04 08:48:51 CST 2018

In Category: NoCategory

Description：

求： $$ \sum_{i=1}^N\sum_{j=1}^Md(ij) $$ $d(x)$ 为 $x$ 的约数个数

Solution：

$$ \begin{align} &\sum_{i=1}^N\sum_{j=1}^Md(ij)\\ &=\sum_{i=1}^N\sum_{j=1}^M\sum_{i'|i}\sum_{j'|j}[gcd(i',j')==1]\\ &=\sum_{i=1}^N\sum_{j=1}^M\sum_{i'|i}\sum_{j'|j}\sum_{d|i'd|j'}\mu(d) \end{align} $$

交换求和号，得：

$$ \sum\mu(d)\sum_{i=1,d|i}^N\sum_{j=1,d|j}^M\sum_{d|i',i'|i}\sum_{d|j',j'|j}1 $$

再交换，得：

$$ \sum\mu(d)\sum_{d|i‘}\sum_{d|j’}\sum_{i=1,d|i,i'|i}^N\sum_{j=1,d|j,j'|j}^M1 $$

放缩，得：

$$ \sum\mu(d)\sum_{i'=1}^{\lfloor\frac N d\rfloor}\sum_{j’=1}^{\lfloor\frac M d\rfloor}\sum_{i=1,di'|i}^N\sum_{j=1,dj'|j}^M1 $$ 再放缩，得：

$$ \sum_d\mu(d)\sum_{i'=1}^{\lfloor\frac N d\rfloor}\sum_{j’=1}^{\lfloor\frac M d\rfloor}\sum_{i=1}^{\lfloor \frac N {di'}\rfloor}\sum_{j=1}^{\lfloor \frac M {dj'}\rfloor}1\\ =\sum_d\mu(d)\sum_{i'=1}^{\lfloor\frac N d\rfloor}\sum_{j’=1}^{\lfloor\frac M d\rfloor}{\lfloor \frac N {di'}\rfloor}{\lfloor \frac M {dj'}\rfloor}\\ =\sum_d\mu(d)\sum_{i'=1}^{\lfloor\frac N d\rfloor}{\lfloor \frac N {di'}\rfloor}\sum_{j’=1}^{\lfloor\frac{M}{d}\rfloor}{\lfloor \frac M {dj'}\rfloor} $$

由于 $\lfloor\lfloor n/i\rfloor/j\rfloor=\lfloor n/(ij)\rfloor$

故： $$ 原式=\sum\mu(d)\sum_{i'=1}^{\lfloor\frac N d\rfloor}{\lfloor \frac{\lfloor\frac N d \rfloor}{i'}\rfloor}\sum_{j’=1}^{\lfloor\frac M d\rfloor}{\lfloor \frac{\lfloor\frac M d \rfloor}{j'}\rfloor} $$ 设 $\begin{align}g(k)=\sum_{i=1}^k{\lfloor\frac k i\rfloor}\end{align}$ $O(N\sqrt N)$ 预处理 $g$ 。

原式 $\begin{align}=\sum\mu(d)g(\lfloor\frac N d\rfloor)g(\lfloor\frac M d\rfloor)\end{align}$

继续分块即可。

Code：


#include

#include

#include

#include

#include

#include

using namespace std;

int testcases;

#define MAXN 50010

int mu[MAXN],prime[MAXN],tot = 0;

bool isprime[MAXN];

typedef long long ll;

ll g[MAXN],sum[MAXN];

void init()

{

	for(int i = 2;i < MAXN;++i)isprime[i] = true;

	mu[1] = 1;

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

	{

		if(isprime[i])

		{

			prime[++tot] = i;

			mu[i] = -1;

		}

		for(int j = 1;j <= tot && i * prime[j] < MAXN;++j)

		{

			isprime[i * prime[j]] = false;

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

			{

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

				break;

			}

			else

			{

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

			}

		}

	}

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

	{

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

		{

			r = i / (i / l);

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

		}

		sum[i] = sum[i - 1] + mu[i];

	}

	return;

}

int n,m;

int main()

{

	init();

	scanf("%d",&testcases);

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

	{

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

		if(n > m)swap(n,m);

		ll ans = 0;

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

		{

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

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

		}

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

	}

	

	return 0;

}

In tag: 数学-莫比乌斯反演

wjh15101051