Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

题意（大概）

(这是一道北航算法课期末题)

已知最大公约数的计算满足结合律，即$gcd(a,b,c)=gcd(a,gcd(b,c))=gcd(gcd(a,b),c)$.

另外计算gcd时有公式 $gcd(a,b)=gcd(b,a\%b)$ ,当第二个参数为0时停止递归.计算不同的两个数字的公约数时就有不同的递归次数.

因此,给定$n$和一连串的数字$a_1,a_2,…,a_n$,使用不同的计算顺序计算$gcd(a_1,…,a_n)$具有不同的递归次数.我们要做的是找到总递归次数最小的计算顺序.

要求第一行输出$gcd(a_1,…,a_n)$的运算结果,第二行输出对应的结合顺序(优先向左结合,格式按照样例),第三行输出递归次数的最小值.具体可参考样例理解.

样例:

输入：

4
1 1 1 1 
复制代码

输出：

1
(((12)3)4)
6
复制代码

样例解释:

$gcd(1,1,1,1)=1$,故第一行输出1.

由于全是1，所以什么顺序计算所需的递归次数都是一样的，但是需要向左优先结合，故如第二行输出,用下标代表对应的数字.

计算一次$gcd(1,1)$需要2次递归,计算$gcd(1,1,1,1)$要算3次$gcd(1,1)$,故递归次数一共为6.

思路

基本思路和矩阵乘法链基本一致(可以参考算法导论的15.2节),动态规划.

先有如下假定:

$gcdn(x,y):计算gcd(x,y)的递归次数,x和y是整数$

$dp1(i,j):gcd(a_i,…,a_j)的最小递归次数$

$dp2(i,j):gcd(a_i,…,a_j)的计算结果$

$dp3(i,j):dp3(i,j)=k$ 即代表 $k$ 是最小计算次数下该次结合的分界点,即若 $gcd(a_i,…,a_j)$ 通过 $gcd(gcd(a_i,…,a_k),gcd(a_{k+1},…,a_j))$ 的方式计算可以获得最小递归次数,那么 $dp3(i,j)=k$

显然 $dp(i,i)$ 为0 , $dp(i,i+1)$ 可以直接计算得出.对于任意 $j>i+1$,我们要做的就是遍历 $i$ 到 $j$ 间的所有分界点 $k$ ,我们假设先通过最优方式计算了 $gcd(a_i,…,a_k)$ 和 $gcd(a_{k+1},…,a_j)$ ,最后就剩这两个计算完毕后剩下的两个数(对应的dp2),最后计算这两个数的gcd.把这个过程的递归次数加起来,对于每个k都计算一遍然后取最小值.由此得到,