P3327 [SDOI2015]约数个数和 解题笔记

原文创建时间：2021-02-13 23:07:38

题目链接

P3327

解题笔记—搬运

首先，有结论
$$\displaystyle d(a,b) = \sum_{i|a}\sum_{j|b}[i \perp j]$$

故原式可化为
$$\displaystyle \sum_{i=1}^N\sum_{j=1}^M\sum_{x|i}\sum_{y|j}[x \perp y]$$

下面作变换：

$\displaystyle = \sum_{i=1}^N\sum_{j=1}^M[i \perp j]\left\lfloor\frac{N}{i}\right\rfloor\left\lfloor\frac{M}{j}\right\rfloor$

$\displaystyle = \sum_{i=1}^N\sum_{j=1}^M\varepsilon(\gcd(i,j))\left\lfloor\frac{N}{i}\right\rfloor\left\lfloor\frac{M}{j}\right\rfloor$

$\displaystyle = \sum_{d=1}^{\min(N,M)}\mu(d)\sum_{i=1}^{\left\lfloor\frac{N}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{M}{d}\right\rfloor}\left\lfloor\frac{N}{di}\right\rfloor\left\lfloor\frac{M}{dj}\right\rfloor$

接下来，反用结论得到

$$\displaystyle \sum_{d=1}^{\min(N,M)}\mu(d)\sum_{i=1}^{\left\lfloor\frac{N}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{M}{d}\right\rfloor}\left\lfloor\frac{\left\lfloor\frac{N}{d}\right\rfloor}{i}\right\rfloor\left\lfloor\frac{\left\lfloor\frac{M}{d}\right\rfloor}{j}\right\rfloor$$

不妨记
$$\displaystyle f(n) = \sum_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor$$

则答案最终为

$$\displaystyle \sum_{d=1}^{\min(N,M)}\mu(d)f\left(\left\lfloor\frac{N}{d}\right\rfloor\right)f\left(\left\lfloor\frac{M}{d}\right\rfloor\right)$$

考虑
$$\displaystyle f(n) = \sum_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor = \sum_{k=1}^nd(k)$$

则用线性筛求出 $\mu$ 和 $d$ 的前缀和即可。

如何用线性筛求 $d$？

根据 $d$ 的定义和性质，以下为通过线性筛求 $d$ 的代码：

void linear_sieve()
{
	d[1] = 1;
	for(int i = 2; i <= bd; ++i) {
		if(!ip[i])
			pr[++pc] = i, k[i] = 1, d[i] = 2;
		for(int j = 1; j <= pc && 1ll * i * pr[j] <= bd; ++j) {
			int num = i * pr[j];
			ip[num] = true;
			if(i % pr[j])
				k[num] = 1, d[num] = d[i] << 1;
			else {
				k[num] = k[i] + 1, d[num] = d[i] / k[num] * (k[num] + 1);
				break;
			}
		}
	}
}

 

---

本题代码

#include<bits/stdc++.h>

using namespace std;

namespace ACAH
{
	typedef long long ll;
	
	const int bd = 5e4 + 7;
	const int maxn = bd + 7;
	
	int T, N, M;
	int pr[maxn], pc;
	bool ip[maxn];
	ll mu[maxn], d[maxn], k[maxn];
	
	void linear_sieve()
	{
		mu[1] = d[1] = 1;
		for(int i = 2; i <= bd; ++i) {
			if(!ip[i])
				pr[++pc] = i, mu[i] = -1, k[i] = 1, d[i] = 2;
			for(int j = 1; j <= pc && 1ll * i * pr[j] <= bd; ++j) {
				int num = i * pr[j];
				ip[num] = true;
				if(i % pr[j])
					k[num] = 1, d[num] = d[i] << 1, mu[num] = -mu[i];
				else {
					k[num] = k[i] + 1, d[num] = d[i] / k[num] * (k[num] + 1);
					break;
				}
			}
		}
		for(int i = 1; i <= bd; ++i)
			mu[i] += mu[i - 1], d[i] += d[i - 1];
	}
	
	inline ll solv(int a, int b)
	{
		ll res = 0;
		for(ll l = 1, r; l <= min(a, b); l = r + 1) {
			r = min(a / (a / l), b / (b / l));
			res += (mu[r] - mu[l - 1]) * d[a / l] * d[b / l];
		}
		return res;
	}
	
	int work()
	{
		linear_sieve();
		scanf("%d", &T);
		while(T--) {
			scanf("%d%d", &N, &M);
			printf("%lld\n", solv(N, M));
		}
		return 0;
	}
}

int main() {return ACAH::work();}