考虑把 \(d(xy)\) 这个玩意拆开。
发现 \(d(xy) = \sum\limits_{i | x} \sum\limits_{j | y} [\gcd(i,j) = 1]\)。
然鹅并不会证明……这里传送到 Siyuan 的证明。
于是题目就是问的 \(\sum\limits_{i=1}^n \sum\limits_{j=1}^m \sum\limits_{x | i} \sum\limits_{y | j} [\gcd(x,y) = 1]\)。
对于上面式子，我们可以转化一下思路：枚举 \(x,y\)，计算其对给定范围内所有数的贡献。
于是有
\[\begin{align*} & \sum\limits_{i=1}^n \sum\limits_{j=1}^m \sum\limits_{x | i} \sum\limits_{y | j} [\gcd(x,y) = 1] \\ = & \sum\limits_{i=1}^n \sum\limits_{j=1}^m \lfloor \dfrac n i \rfloor \lfloor \dfrac m j \rfloor [\gcd(i,j) = 1] \end{align*}\]
然后设 \(f(x) = \sum\limits_{i=1}^n \sum\limits_{j=1}^m \lfloor \dfrac n i \rfloor \lfloor \dfrac m j \rfloor [\gcd(i,j) = x],F(x) = \sum\limits_{x | i} f(i) = \sum\limits_{i=1}^n \sum\limits_{j=1}^m \lfloor \dfrac n i \rfloor \lfloor \dfrac m j \rfloor [x | \gcd(i,j)]\)。
\[\begin{align*} & \sum\limits_{i=1}^n \sum\limits_{j=1}^m \lfloor \dfrac n i \rfloor \lfloor \dfrac m j \rfloor [x | \gcd(i,j)] \\ = & \sum\limits_{xi \le n} \sum\limits_{xj \le m} \lfloor \dfrac n {xi} \rfloor \lfloor \dfrac m {xj} \rfloor \end{align*}\]
那么有 \(f(x) = \sum\limits_{x | i} \mu(\dfrac i x) F(i)\)，此题求 \(f(1) = \sum\limits_{i=1}^n \mu(i) F(i) = \sum\limits_{i=1}^n \mu(i) \sum\limits_{xi \le n} \lfloor \dfrac {\lfloor \frac n x \rfloor} i \rfloor \sum\limits_{yi \le m} \lfloor \dfrac {\lfloor \frac m y \rfloor} i \rfloor\)。
对于任意的 \(n\)，预处理一下 \(\sum\limits_{i = 1}^n \lfloor \dfrac n i \rfloor\) 和 \(\mu\) 的前缀和然后数论分块。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
using namespace std;
const int N = 5e4;
int t;
int cnt,prime[N + 5],mu[N + 5],vis[N + 5];
long long sum[N + 5];
int main()
{
mu[1] = 1;
for(register int i = 2;i <= N;++i)
{
if(!vis[i])
prime[++cnt] = i,mu[i] = -1;
for(register int j = 1;j <= cnt && i * prime[j] <= N;++j)
{
vis[i * prime[j]] = 1;
if(!(i % prime[j]))
break;
else
mu[i * prime[j]] = -mu[i];
}
}
for(register int i = 1;i <= N;++i)
{
mu[i] += mu[i - 1];
for(register int l = 1,r;l <= i;l = r + 1)
{
r = i / (i / l);
sum[i] += (long long)(i / l) * (r - l + 1);
}
}
scanf("%d",&t);
int n,m;
long long ans;
while(t--)
{
ans = 0;
scanf("%d%d",&n,&m);
if(n > m)
swap(n,m);
for(register int l = 1,r;l <= n;l = r + 1)
{
r = min(n / (n / l),m / (m / l));
ans += (long long)(mu[r] - mu[l - 1]) * sum[n / l] * sum[m / l];
}
printf("%lld\n",ans);
}
}