【bzoj2694】Lcm 莫比乌斯反演+线性筛

题目描述

求$\sum\limits_{i=1}^n\sum\limits_{j=1}^m|\mu(gcd(i,j))|lcm(i,j)$，即$gcd(i,j)$不存在平方因子的$lcm(i,j)$之和。

输入

一个正整数T表示数据组数

接下来T行每行两个正整数表示N、M

输出

T行每行一个整数表示第i组数据的结果

样例输入

4
2 4
3 3
6 5
8 3

样例输出

24
28
233
178

题解

莫比乌斯反演+线性筛

（为了方便，以下公式默认$n\le m$）

$\ \ \ \ \sum\limits_{i=1}^n\sum\limits_{j=1}^m|\mu(gcd(i,j))|lcm(i,j)\\=\sum\limits_{d=1}^n|\mu(d)|\sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)=d]\frac{ij}d\\=\sum\limits_{d=1}^n|\mu(d)|\sum\limits_{i=1}^{\lfloor\frac nd\rfloor}\sum\limits_{j=1}^{\lfloor\frac md\rfloor}[gcd(i,j)=1]ijd\\=\sum\limits_{d=1}^nd|\mu(d)|\sum\limits_{i=1}^{\lfloor\frac nd\rfloor}i\sum\limits_{j=1}^{\lfloor\frac md\rfloor}j\sum\limits_{p|gcd(i,j)}\mu(p)\\=\sum\limits_{d=1}^nd|\mu(d)|\sum\limits_{p=1}^{\lfloor\frac nd\rfloor}\mu(p)\sum\limits_{i=1}^{\lfloor\frac n{dp}\rfloor}ip\sum\limits_{j=1}^{\lfloor\frac m{dp}\rfloor}jp\\=\sum\limits_{d=1}^nd|\mu(d)|\sum\limits_{p=1}^{\lfloor\frac nd\rfloor}p^2\mu(p)s(\lfloor\frac n{dp}\rfloor)s(\lfloor\frac m{dp}\rfloor)$

其中$s(n)=\sum\limits_{i=1}^ni$

然后再令$D=dp$，可以得到：

$\ \ \ \ \sum\limits_{d=1}^nd|\mu(d)|\sum\limits_{p=1}^{\lfloor\frac nd\rfloor}p^2\mu(p)s(\lfloor\frac n{dp}\rfloor)s(\lfloor\frac m{dp}\rfloor)\\=\sum\limits_{D=1}^ns(\lfloor\frac nD\rfloor)s(\lfloor\frac mD\rfloor)\sum\limits_{p|D}p^2\mu(p)·\frac Dp|\mu(\frac Dp)|\\=\sum\limits_{D=1}^nD·s(\lfloor\frac nD\rfloor)·s(\lfloor\frac mD\rfloor)\sum\limits_{p|D}p·\mu(p)·|\mu(\frac Dp)|$

设后面的式子为$f(D)$，那么其为积性函数，因此可以快筛。具体方法：当$D$为质数时为$f(D)=1-D$，否则将$D$分解为$vp^a$，其中$p$为最小质因子。当$a\ge3$时$f(p^a)$一定等于0，否则直接计算即可。

之后求前缀和，分块处理即可。

时间复杂度$O(n+T\sqrt{n})=O(能过)$

其中本题的对$2^{30}$取模，可以直接自然溢出uint，然后最后的答案&$2^{30}-1$

#include <cstdio>

#include <algorithm>

#define N 4000010

#define k 4000000

using namespace std;

unsigned f[N] , prime[N] , tot , np[N] , sum[N];

inline unsigned s(unsigned n)

{

	return n * (n + 1) / 2;

}

int main()

{

	unsigned i , j , n , m , last , ans;

	int T;

	sum[1] = f[1] = 1;

	for(i = 2 ; i <= k ; i ++ )

	{

		if(!np[i]) f[i] = 1 - i , prime[++tot] = i;

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

		{

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

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

			{

				if(i / prime[j] % prime[j] == 0) f[i * prime[j]] = 0;

				else f[i * prime[j]] = -f[i / prime[j]] * prime[j];

				break;

			}

			else f[i * prime[j]] = f[i] * f[prime[j]];

		}

		sum[i] = sum[i - 1] + f[i] * i;

	}

	scanf("%d" , &T);

	while(T -- )

	{

		scanf("%u%u" , &n , &m) , ans = 0;

		for(i = 1 ; i <= n && i <= m ; i = last + 1)

			last = min(n / (n / i) , m / (m / i)) , ans += s(n / i) * s(m / i) * (sum[last] - sum[i - 1]);

		printf("%u\n" , ans & ((1 << 30) - 1));

	}

	return 0;

}

巴特西

【bzoj2694】Lcm 莫比乌斯反演+线性筛

最新文章

热门文章