题解

思路

设 $c_d$ 为数组中能被 $d$ 整除的数的个数。只从这 $c_d$ 个位置中选取时，所有非空子序列的长度总和为

这会同时统计最大公约数等于 $d,2d,3d,\ldots$ 的子序列。令 $f_d$ 为最大公约数恰好等于 $d$ 的所有子序列长度之和，从大到小计算

答案即为 $\sum_{d\ge2}d f_d$。

做法

当 $n\le20$ 时，可以枚举全部非空子集并直接计算最大公约数。值域和元素数较小时，也可以逐个加入元素，按当前子序列的最大公约数维护子序列数量与长度总和。满分做法利用倍数枚举和从大到小的容斥。

正确性说明

所有元素都能被 $d$ 整除的非空子序列，按其最大公约数恰好等于 $d$ 的某个正整数倍被唯一分类。因此，从 $c_d2^{c_d-1}$ 中减去所有真倍数对应的 $f$ 值后，剩余量恰为 $f_d$。每个合法氏族的最大公约数大于一，它在最终求和中恰好贡献一次“长度乘最大公约数”，故所得结果正是题目要求的军队力量。

复杂度

设 $V=\max a_i$。时间复杂度为 $O(V\log V+n)$，空间复杂度为 $O(V+n)$。