洛谷P3327 莫比乌斯反演，约数函数结论

题意：

给出$n,m$，计算
$$\sum _{i=1}^n\sum _{j=1}^{m}d(ij)$$
其中$d(x)$是$x$的约数个数

Solution：

有一条结论

$$d(ij)=\sum _{x|i}\sum _{y|j}[gcd(x,y)=1]$$

那么即计算
$$\sum _{i=1}^n\sum _{j=1}^m\sum _{x|i}\sum _{y|j}[gcd(x,y)=1]$$
莫比乌斯反演得到
$$\sum _{i=1}^n\sum _{j=1}^m\sum _{x|i}\sum _{y|j}\sum _{d|gcd(x,y)}\mu (d)$$
优先枚举因子，这里有$x,i$是因子和因子的因子，优先枚举更因子的因子$d$，这样$x$就是$d$的倍数，$i$就是$x$的倍数，
$$\sum _{d=1}^n\mu (d)(\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }\sum _{j=1}^{\lfloor \frac{n}{id}\rfloor }1)(\sum _{i=1}^{\lfloor \frac{m}{d}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{id}\rfloor }1)=\sum _{d=1}^n\mu (d)(\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }\lfloor \frac{n}{id}\rfloor )(\sum _{i=1}^{\lfloor \frac{m}{d}\rfloor }\lfloor \frac{m}{id}\rfloor )\text{\hspace{1em}(1)}$$
令
$$f(x)=\sum _{i=1}^x\lfloor \frac{x}{i}\rfloor$$
原式即
$$\sum _{d=1}^n\mu (d)f(\lfloor \frac{n}{d}\rfloor )f(\lfloor \frac{m}{d}\rfloor )$$
显然这个式子可以数论分块，每个$f(x)$也可以数论分块，此时总复杂度是$O(Tn)$，发现每个$f(x)$可以预处理出来，那么时间复杂度就降到了$O(n\sqrt{n}+T\sqrt{n})$

$(1)$式需要注意的地方是，枚举$d$的倍数作为$x$，$x$的倍数作为$i$（这里的$x,i$都是对$(1)$式之前而言的），一开始做的时候把$i$看成比$x$大的$d$的倍数就可以了，实际上这是不一定的，比如说$x=3d,i=7d$，$x$并不能整除$i$，所以$(1)$式的左式的每个括号内的第二个求和的上标发生了变化。可能是练太少了，一些细节还是难注意到

// #include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
using ll=long long;
const int N=5e4+5;

int mu[N],prime[N],cnt,sum[N];
bool nt[N];

ll f[N];

ll calc(int x)
{
    ll ret=0;
    for(int l=1,r;l<=x;l=r+1)
    {
        r=x/(x/l);
        ret+=x/l*(r-l+1);
    }
    return ret;
}

void make_prime()
{
    mu[1]=1;
    for(int i=2;i<=50000;i++)
    {
        if(!nt[i]) prime[++cnt]=i,mu[i]=-1;
        for(int j=1;j<=cnt&&i*prime[j]<=50000;j++)
        {
            nt[i*prime[j]]=true;
            if(i%prime[j]==0) break;
            else mu[i*prime[j]]=mu[i]*mu[prime[j]];
        }
    }
    for(int i=1;i<=50000;i++)
    {
        sum[i]=sum[i-1]+mu[i];
        f[i]=calc(i);
    }
}

int main()
{
    make_prime();
    int t; cin>>t;
    while(t--)
    {
        ll ans=0;
        int n,m; cin>>n>>m;
        if(n>m) swap(n,m);
        for(int l=1,r;l<=n;l=r+1)
        {
            r=min(n/(n/l),m/(m/l));
            ans+=f[n/l]*f[m/l]*(sum[r]-sum[l-1]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}
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
62
63
64
65
66
67