J-有点复杂的gcd问题_第一届河北工业大学程序设计竞赛校赛（同步赛）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

竭泽十分喜欢数论，并且在莫比乌斯反演点了很多奇怪的技能点

在介绍这个问题之前，竭泽会给大家介绍一点数论常识常见的数论符号和数论解题trick

$gcd(i, j)$ 表示i和j的最大公因数
[n == 1] 这个符号表示，若n == 1，则返回1，否则返回0
$\mu$ (i)是莫比乌斯函数，, 其中 $p_i$ 为质因数
狄利克雷卷积我们定义 * 为狄利克雷卷积符号，那么 $h(n) = (f * g)(n) = \sum_{d|n} f(d)g(\frac{n}{d})$
莫比乌斯反演
其中有一个重要性质
$\sum_{d|n} \mu(d) = [n==1]$

前置知识一看就很简单，竭泽还想给大家看看经典的莫比乌斯反演的例子,就是运算下列式子

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

$0 \leq n \lt m \leq 10^6$

这时候如果我们直接遍历肯定会TLE，那么试试神奇的莫比乌斯反演，在这之前，我们先整理一下式子

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

我们同时除以k，得到

$\sum_{i=1}^{\lfloor n/k \rfloor} \sum_{j=1}^{\lfloor m/k \rfloor} [gcd(i, j) == 1]$

这时候我们发现[gcd(i, j) == 1]很像[n == 1]，这时候想到 $\sum_{d|n} \mu(d) = [n==1]$

于是我们尝试着枚举一个新的数字d，使得d|gcd(i, j),从而得到

$\sum_{i=1}^{\lfloor n/k \rfloor} \sum_{j=1}^{\lfloor m/k \rfloor} \sum_{d|gcd(i, j)} \mu (d)$

其实我们很轻易的就可以知道d的枚举范围其实是[1, n/k ], 那么这个式子就可以改写成

$\sum_{i=1}^{\lfloor n/k \rfloor} \sum_{j=1}^{\lfloor m/k \rfloor} \sum_{d=1}^{\lfloor n/k \rfloor} \mu (d) [d|gcd(i, j)]=\sum_{i=1}^{\lfloor n/k \rfloor} \sum_{j=1}^{\lfloor m/k \rfloor} \sum_{d=1}^{\lfloor n/k \rfloor} \mu (d) [d|i] [d|j]$

我们更换一下顺序

$\sum_{d=1}^{\lfloor n/k \rfloor} \mu (d) \sum_{i=1}^{\lfloor n/k \rfloor} [d|i] \sum_{j=1}^{\lfloor m/k \rfloor} [d|j]$

我们看到 $\sum_{i=1}^{\lfloor n/k \rfloor} [d|i]$ ,换成人话就是说 n/k 里面有多少个是d的倍数，那其实很轻易知道这个式子的值是 $\lfloor \frac{n}{kd} \rfloor$ ,(比如说10里面有多少个3的倍数当然是10/3啦)

所以式子可以写为

$\sum_{d=1}^{\lfloor n/k \rfloor} \mu (d) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor$

这样就不会超时了

整理一下过程

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

= $\sum_{i=1}^{\lfloor n/k \rfloor} \sum_{j=1}^{\lfloor m/k \rfloor} [gcd(i, j) == 1]$

= $\sum_{i=1}^{\lfloor n/k \rfloor} \sum_{j=1}^{\lfloor m/k \rfloor} \sum_{d|gcd(i, j)} \mu (d)$

= $\sum_{i=1}^{\lfloor n/k \rfloor} \sum_{j=1}^{\lfloor m/k \rfloor} \sum_{d=1}^{\lfloor n/k \rfloor} \mu (d) [d|gcd(i, j)]$

= $\sum_{i=1}^{\lfloor n/k \rfloor} \sum_{j=1}^{\lfloor m/k \rfloor} \sum_{d=1}^{\lfloor n/k \rfloor} \mu (d) [d|i] [d|j]$

= $\sum_{d=1}^{\lfloor n/k \rfloor} \mu (d) \sum_{i=1}^{\lfloor n/k \rfloor} [d|i] \sum_{j=1}^{\lfloor m/k \rfloor} [d|j]$

= $\sum_{d=1}^{\lfloor n/k \rfloor} \mu (d) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor$

这里给出莫比乌斯线性筛的函数

const int maxn=1e6+5;
bool vis[maxn];
int prime[maxn],mu[maxn];
void init_mu(int n){//init_mu(n) 就可得到1-n的莫比乌斯函数的值，存在mu中
    int cnt=0;
    mu[1]=1;
    for(int i=2;i<n;i++){
        if(!vis[i]){
            prime[cnt++]=i;
            mu[i]=-1;
        }
        for(int j=0;j<cnt&&i*prime[j]<n;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)   {mu[i*prime[j]]=0;break;}
            else { mu[i*prime[j]]=-mu[i];}
        }
    }
}

使用这个函数之后 $\mu (i) = mu[i]$ ，可以用这个函数存放莫比乌斯函数的值

介绍完了简单的例题，竭泽决定考考大家一个和上述例题非常相似的题目，看看大家是否都掌握了，是否都能举一反三，是否能看清事情的本质

竭泽定义了一个函数

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

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

$f(a_1, a_2, a_3, . . ., a_k) = \sum_{a_1 = 1}^{n} \sum_{a_2=1}^{a_1} \sum_{a_3=1}^{a_2} . . . \sum_{a_k=1}^{a_{k-1}} [gcd(a_1, a_2, a_3, . . ., a_k) == a_1]$

竭泽再定义一个函数

$g(a_1, a_2, a_3, . . ., a_k) = \sum_{a_1 = 1}^{n} \sum_{a_2=1}^{a_1} \sum_{a_3=1}^{a_2} . . . \sum_{a_k=1}^{a_{k-1}} \lbrace[gcd(a_1, a_2, a_3, . . ., a_k) == a_1] * a_k\rbrace$