love math love gcd

发表于 |

关于gcd的博文已经写过三篇了，为什么还要写呢？(任意中文输入法下输入gcd)你就懂了0.0

计算 $f(n) = \sum_{i=1}^n \sum_{j=1}^n [gcd(i,j)==1]$

这里给出 $f(n)$ 的两个计算公式。

$$
n^2 = \sum_{d=1}^n \sum_{i=1}^{n} \sum_{j=1}^n [gcd(i,j)==d] =
\sum_{d=1}^n \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{n}{d} \rfloor} [gcd(i,j)==1] = \sum_{d=1}^n f(\lfloor \frac{n}{d} \rfloor)
$$
因此由之前的博文可用记忆化搜索的方法求出$f(n)$

$$
f(n) = \sum_{i=1}^n \sum_{j=1}^n [gcd(i,j)==1] =
\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{d|i,d|j} \mu(d) = \sum_{d=1}^n \mu(d) (\lfloor \frac{n}{d} \rfloor)^2
$$
因此由博文 在预处理后可根号算法快速求出。
实际上，$f(n)$ 还有一个表达式。
$$ f(n)= 2 \sum_{i=1}{n} \phi(i) - 1 $$

为什么两个完全不同的式子都可以计算呢。实际上这是由广义Dirchilet 性质决定的。

hdu5663一个更复杂的例子

计算 $r(n,m)=\sum_{i=1}^n \sum_{j=1}^m f(gcd(i,j))$，其中$f(n)＝0$ 若 $n$ 是平方数，否则为 $1$。
解：我们不妨设 $n \leq m$。
$$
\begin{aligned}
r(n,m) &=\sum_{i=1}^n \sum_{j=1}^m f(gcd(i,j)) \\
&= \sum_{d=1}^n f(d) \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} \sum_{t|i,t|j} \mu(t) \\
&= \sum_{d=1}^n f(d) \sum_{t=1}^{\lfloor \frac{n}{d} \rfloor} \mu(t) \lfloor \frac{n}{dt} \rfloor \lfloor \frac{m}{dt} \rfloor \\
&= \sum_{G=1}^n \lfloor \frac{n}{G} \rfloor \lfloor \frac{m}{G} \rfloor \sum_{t|G} \mu(t)f(\frac{G}{t})
\end{aligned}
$$
据此，我们可以给出下面代码。(上面过程技巧性很强，要充分利用 $\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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
//#pragma comment(linker,"/STACK:10240000,10240000")
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
#define clr(a,b) memset(a,b,sizeof(a))
#define MP make_pair
#define PB push_back
#define lrt rt<<1
#define rrt rt<<1|1
#define lson l,m,lrt
#define rson m+1,r,rrt
/*------ Welcome to visit blog of dna049: http://dna049.com ------*/
const int N = 1e7+2;
int mu[N],g[N],p[N],np[N],cnt;
void init(){
    mu[1] = 1;
    for(int i = 2; i < N; ++i) {
        if(!np[i]) {
            p[cnt++] = i;
            mu[i] = -1;
        }
        for(int j = 0;j < cnt && i * p[j] < N; ++j) {
            int t = i * p[j];
            np[t] = 1;
            if(i % p[j])   mu[t] = -mu[i];
        }
    }
    for(int i=1;i*i<N;++i){
        for(int j=1;i*i*j<N;++j){
            g[i*i*j] += mu[j];
        }
    }
    for(int i=2;i<N;++i)    g[i]+=g[i-1];
}
int main(){
//    freopen("/Users/dna049/Desktop/AC/in","r",stdin);
//    freopen("/Users/dna049/Desktop/AC/out","w",stdout);
    init();
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        LL ans = LL(n)*m;
        for(int i=1,j;i<=min(n,m);i=j+1){
            j=min(n/(n/i),m/(m/i));
            ans -= LL(n/i)*(m/i)*(g[j]-g[i-1]);
        }
        cout<<ans<<endl;
    }
    return 0;
}