LuoguP3327「SDOI2015」题解

发表于

还是经典的Mobius反演

题目描述

设$d(x)$为$x$的约数个数，给出多组$n,m$,求式子：

$$\sum_{i=1}^n \sum_{j=1}^m d(ij)$$

的值。

Input & Output’s examples

Input’s e.g. #1

1
2
3
2
7 4
5 6

Output’s e.g. #1

1
2
110
121

分析

首先我们要知道$d(x)$函数的一个性质：

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

然后就可以愉快的推式子了qwq，把这个东西代入原式可得：

$$\sum_{i=1}^n \sum_{j=1}^m \sum_{x|i} \sum_{y|j} [\gcd(x,y) = 1]$$

根据Mobius函数的定义式，我们可以化简原式得：

$$\sum_{i=1}^n \sum_{j=1}^m \sum_{x|i} \sum_{y|j} \sum_{d|\gcd(x,y)} \mu(d)$$

我们改变枚举对象，直接枚举$d$:

$$\sum_{i=1}^n \sum_{j=1}^m \sum_{x|i} \sum_{y|j} \sum_{d=1}^{\min(n,m)} [d|\gcd(x,y)] \cdot \mu(d)$$

然后我们改变枚举顺序。

$$\sum_{d=1}^{\min(n,m)} \mu(d) \sum_{i=1}^n \sum_{j=1}^m \sum_{x|i} \sum_{y|j} [d|\gcd(x,y)]$$

然后我们不再枚举$i,j$和他们的约数,而是枚举这些约束直接乘上他们的倍数的个数，因为这些约数只会对他们的倍数有贡献。

$$\sum_{d=1}^{\min(n,m)} \mu(d) \sum_{i=1}^n \sum_{j=1}^m [d|\gcd(x,y)] \lfloor \frac nx\rfloor \lfloor \frac my\rfloor$$

同时除一下$d$:

$$\sum_{d=1}^{\min(n,m)} \mu(d) \sum_{i=1}^{\lfloor \frac nd\rfloor} \sum_{j=1}^{\lfloor \frac md\rfloor} [\gcd(x,y) \in Z] \lfloor \frac nx\rfloor \lfloor \frac my\rfloor$$

显然$\gcd(x,y) \in Z$恒成立，那么直接去掉：

$$\sum_{d=1}^{\min(n,m)} \mu(d) \sum_{i=1}^{\lfloor \frac nd\rfloor} \sum_{j=1}^{\lfloor \frac my\rfloor} \lfloor \frac nx\rfloor \lfloor \frac my\rfloor$$

然后我们根据乘法分配律：

$$\sum_{d=1}^{\min(n,m)} \mu(d) \left( \sum_{i=1}^{\lfloor \frac nd\rfloor} \lfloor \frac nx\rfloor \right) \left( \sum_{j=1}^{\lfloor \frac my\rfloor} \lfloor \frac my\rfloor \right)$$

显然括号内的式子可以进行一下数论分块，然后本题就愉快的结束了qwq

代码

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const int MAXN = 5e4 + 2;
int T,n,m,cnt;
int prime[MAXN],u[MAXN],sum[MAXN];
long long G[MAXN];
bool isprime[MAXN];
/* functions */
inline void init(int n){
    u[1] = 1;
    FOR(i,2,n,1){
        if(!isprime[i]) u[i] = -1, prime[++cnt] = i;
        for(int j=1;j <= cnt && i * prime[j] <= n;j++){
            isprime[i * prime[j]] = true;
            if(i % prime[j] == 0) break;
            else u[i * prime[j]] = -u[i];
        }
    }
    FOR(i,1,n,1) sum[i] = sum[i-1] + u[i];
    FOR(i,1,n,1){
        long long ans = 0;
        for(int l=1,r;l<=i;l=r+1){
            r = (i/(i/l));
            ans += 1ll * (r - l + 1) * 1ll * (i/l);
        }
        G[i] = ans;
    }
}
int main(int argc,char *argv[]){
    read(T);
    init(MAXN);
    while(T--){
        static int n,m;
        read(n), read(m);
        static int d = std::min(n,m);
        static long long ans = 0ll;
        for(int l=1,r;l<=d;l=r+1){
            r = std::min(n/(n/l),m/(m/l));
            ans += (sum[r] - sum[l-1]) * 1ll * G[n/l] * 1ll * G[m/l];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

THE END