题目描述

求$\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 
     
      #include 
      
       #define N 4000010#define k 4000000using 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;}