SDOI2015约数个数和

Posted on Edited on In Word count in article: 516 Reading time ≈ 2 mins.
莫比乌斯反演好题

[SDOI2015]约数个数和

题目简述

求： \[ \sum_{i=1}^n\sum_{j=1}^m\sigma(ij) \]

分析

\[ \sigma(ij)=\sum_{x|i}\sum_{y|j}[x\perp y] \]

证明： \[ i=\prod_{k=1}{p_k}^{a_k},j=\prod_{k=1}{p_k}^{b_k}\\ ij=\prod_{k=1}{p_k}^{a_k+b_k},\sigma(ij)=\prod_{k=1}(a_k+b_k+1) \] 所以说，可以有这样的假设：

  • 当 \(x\perp y\;\;\land {a_k}^\prime>0\) 时，\(x\times y\) 的 \(p_k\) 的指数就是 \({a_k}^\prime\)。
  • 当 \(x\perp y\;\;\land {b_k}^\prime>0\) 时，\(x\times y\) 的 \(p_k\) 的指数就是 \(a_k+{b_k}^\prime\)

所以这样可以不重不漏的枚举出所有 \(ij\) 的约数。

化简

所以原式可以化为： \[ \begin{aligned} \sum_{i=1}^n\sum_{j=1}^m\sigma(ij)&=\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[x\perp y]\\ &=\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}\sum_{d|\gcd(x,y)}\mu(d)\\ &=\sum_{d=1}^n\mu(d)\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac md\rfloor}\sigma(i)\sigma(j)\\ &=\sum_{d=1}^n\mu(d)\sum_{i=1}^{\lfloor\frac nd\rfloor}\sigma(i)\sum_{j=1}^{\lfloor\frac md\rfloor}\sigma(j)\\ &=\sum_{d=1}^n\mu(d)g(\lfloor\frac nd\rfloor)g(\lfloor\frac md\rfloor) \end{aligned} \] 所以就是 \(O(n)\) 的预处理 \(+\;O(T\sqrt n)\) 的查询，这道题就愉快的结束了。

Code

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
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int Maxn = 5e4;
int Cnt, Prim[Maxn + 5], Mu[Maxn + 5], C[Maxn + 5];
ll D[Maxn];
bool Vis[Maxn + 5];
int T, N, M;

inline void Init()
{
    Mu[1] = D[1] = C[1] = 1;
    for (int i = 2; i <= Maxn; ++i)
    {
        if (!Vis[i]) Prim[++Cnt] = i, Mu[i] = -1, C[i] = 1, D[i] = 2;
        for (int j = 1; j <= Cnt && i * Prim[j] <= Maxn; ++j)
        {
            Vis[i * Prim[j]] = 1;
            if (i % Prim[j] == 0)
            {
                D[i * Prim[j]] = D[i] / (C[i] + 1) * (C[i] + 2);
                C[i * Prim[j]] = C[i] + 1;
                break;
            }
            Mu[i * Prim[j]] = -Mu[i];
            D[i * Prim[j]] = D[i] << 1;
            C[i * Prim[j]] = 1;
        }
		Mu[i] += Mu[i - 1], D[i] += D[i - 1];
    }
}

inline int read()
{
	int x(0);
	char o(getchar());
	while (o < '0' || o > '9') o = getchar();
	for (; o >= '0' && o <= '9'; o = getchar())
		x = (x << 1) + (x << 3) + (o ^ 48);
	return x;
}

int main()
{
    Init();
	T = read();    
	while (T--)
    {
		N = read(), M = read();        
		if (N > M) swap(N, M);
        ll Ans(0);
        for (int l = 1, r; l <= N; l = r + 1)
        {
            r = min(N / (N / l), M / (M / l));
            Ans += (Mu[r] - Mu[l - 1]) * D[N / l] * D[M / l];
        }
        printf("%lld\n", Ans);
    }
}