题解 SP26108 【TRENDGCD - Trending GCD】
Warriors_Cat
2020-12-04 08:56:23
莫比乌斯反演基础题。
----
### $Solution:$
以下默认 $n \le m$，$N$ 为 $n, m$ 上限。
推式子过程有些简略，建议有一定基础再来看。
$$\begin{aligned}\text{原式}&=\sum_{i=1}^n\sum_{j=1}^mij\gcd(i, j)\mu^2(\gcd(i,j))\\&=\sum_{d=1}^nd^3\mu^2(d)\sum_{i=1}^{\left\lfloor{\frac{n}{d}}\right\rfloor}\sum_{j=1}^{\left\lfloor{\frac{m}{d}}\right\rfloor}ij[\gcd(i, j)=1]\\&=\sum_{d=1}^nd^3\mu^2(d)\sum_{i=1}^{\left\lfloor{\frac{n}{d}}\right\rfloor}\sum_{j=1}^{\left\lfloor{\frac{m}{d}}\right\rfloor}ij\sum_{k\mid\gcd(i, j)}\mu(k)\\&=\sum_{d=1}^nd^3\mu^2(d)\sum_{k=1}^{\left\lfloor{\frac{n}{d}}\right\rfloor}\mu(k)k^2\sum_{i=1}^{\left\lfloor{\frac{n}{kd}}\right\rfloor}\sum_{j=1}^{\left\lfloor{\frac{m}{kd}}\right\rfloor}ij\end{aligned}$$
令 $S(n) =\dfrac{n(n+1)}{2}$。
$$\begin{aligned}\text{原式}&=\sum_{d=1}^n\sum_{k=1}^{\left\lfloor{\frac{n}{d}}\right\rfloor}d^3k^2\mu^2(d)\mu(k)S(\left\lfloor{\frac{n}{kd}}\right\rfloor)S(\left\lfloor{\frac{m}{kd}}\right\rfloor)\\&=\sum_{T=1}^n \sum_{d\mid T}d^3(\frac{T}{d})^2\mu^2(d)\mu(\frac{T}{d})S(\left\lfloor{\frac{n}{T}}\right\rfloor)S(\left\lfloor{\frac{m}{T}}\right\rfloor)\\&=\sum_{T=1}^nT^2\sum_{d\mid T}d\mu^2(d)\mu(\frac{T}{d})S(\left\lfloor{\frac{n}{T}}\right\rfloor)S(\left\lfloor{\frac{m}{T}}\right\rfloor)\end{aligned}$$
令 $f(T)=\sum_{d\mid T}d\mu^2(d)\mu(\frac{T}{d})$，显然 $f(T)$ 是积性函数。
$$\text{原式}=\sum_{T=1}^nT^2f(T)S(\left\lfloor{\frac{n}{T}}\right\rfloor)S(\left\lfloor{\frac{m}{T}}\right\rfloor)$$
我们通过一些手段，式子到这里就可以数论分块了，所以我们的目的就是把 $f$ 函数线性筛。
若 $\exists p \in \mathbb{P}\ s.t.\ p^3\mid n$，那么 $\mu(p)$ 和 $\mu(\dfrac{n}{d})$ 中必有一个为 $0$，那一项就不用看了。
于是我们只要考虑 $f(1)$，$f(p)$，$f(p^2)$ 就行。
$$f(1)=1$$
$$f(p)=1\mu^2(1)\mu(p)+p\mu^2(p)\mu(1)=p-1$$
$$f(p^2)=1\mu^2(1)\mu(p^2)+p\mu^2(p)\mu(p)+p^2\mu^2(p^2)\mu(1)=-p$$
可以线性筛了。
over，时间复杂度为 $O(N + T\sqrt{N})$。
---
### $Code:$
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;
#define ll long long
#define fi first
#define se second
#define x1 x_csyakioi_1
#define x2 x_csyakioi_2
#define y1 y_csyakioi_1
#define y2 y_csyakioi_2
#define y0 y_csyakioi_0
#define dingyi int mid = l + r >> 1, ls = p << 1, rs = p << 1 | 1;
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 1000010, mod = 1000000007;
int t, n, m, pri[N], len, f[N]; bool vis[N];
inline void sieve(int n){
f[1] = 1;
for(int i = 2; i <= n; ++i){
if(!vis[i]) pri[++len] = i, f[i] = i - 1;
for(int j = 1; j <= len && i * pri[j] <= n; ++j){
int k = i * pri[j]; vis[k] = 1;
if(i % pri[j] == 0){
if((i / pri[j]) % pri[j] != 0) f[k] = 1ll * f[i / pri[j]] * (mod - pri[j]) % mod;
else f[k] = 0;
break;
}
f[k] = 1ll * f[i] * f[pri[j]] % mod;
}
}
for(int i = 1; i <= n; ++i) f[i] = (f[i - 1] + 1ll * f[i] * i % mod * i % mod) % mod;
}
inline int sum1(int x){ return 1ll * x * (x + 1) / 2 % mod; }
inline void work(){
n = read(); m = read();
if(n > m) swap(n, m); int ans = 0;
for(int i = 1, j; i <= n; i = j + 1){
j = min(n / (n / i), m / (m / i));
ans = (ans + 1ll * (f[j] - f[i - 1] + mod) % mod * sum1(n / i) % mod * sum1(m / i) % mod) % mod;
}
printf("%d\n", ans);
}
int main(){
t = read(); sieve(N - 10);
while(t--) work();
return 0;
}
```