Serval 与音乐游戏：题解

思路

记 $N=s_n$。交换求和顺序后，问题等价于对每个 $x$ 求有多少个 $s_i$ 能由 $\lfloor N/x\rfloor$ 与 $\lceil N/x\rceil$ 的非负整数线性组合表示。

非整除情形

当 $x\nmid N$ 时，令 $k=\lfloor N/x\rfloor$，则两个数为 $k,k+1$。把

$$s_i=ak+r,\qquad 0\le r<k$$

写成

$$s_i=(a-r)k+r(k+1)$$

可知它可表示当且仅当 $r\le a$，即

$$s_i\bmod k\le\left\lfloor\frac{s_i}{k}\right\rfloor.$$

不可表示的数恰落在下列区间中：

$$[1,k-1],[k+2,2k-1],\ldots, [jk+j+1,(j+1)k-1].$$

用值域前缀和即可在常数时间内统计一个区间含有多少个 $s_i$。

具有相同 $k=\lfloor N/x\rfloor$ 的 $x$ 构成连续区间

$$\left[\left\lfloor\frac{N}{k+1}\right\rfloor+1, \left\lfloor\frac Nk\right\rfloor\right].$$

整除点 $x=N/k$ 若存在，需要从该区间的权值和中暂时删去，交给下一类单独计算。

整除情形

当 $x\mid N$ 时，令 $k=N/x$，两个生成数都等于 $k$，所以 $s_i$ 可表示当且仅当 $k\mid s_i$。

计算 $g_i=\gcd(s_i,N)$。对每个 $N$ 的因子 $k$，统计有多少个 $g_i$ 是 $k$ 的倍数，即可得到对应 $x=N/k$ 的 $f(x)$。

做法

1. 建立序列值域的出现次数前缀和，并统计所有 $\gcd(s_i,N)$ 的频次。
2. 按整除分块枚举所有不同的 $k=\lfloor N/x\rfloor$。对每个 $k$ 枚举不可表示区间，用前缀和得到失败数量，再乘该块中所有非整除 $x$ 的和。
3. 枚举 $N$ 的每个因子 $k$，累加所有为 $k$ 倍数的最大公因数频次，并加入权值 $N/k$ 的贡献。

小规模子任务可以直接枚举 $p_i,q_i$；中规模子任务可以对每对 $(x,s_i)$ 使用余数判据；满分算法才使用整除分块、区间前缀和与因子汇总。

正确性证明

引理 1：若 $x\nmid N$ 且 $k=\lfloor N/x\rfloor$，则 $s_i$ 可表示当且仅当 $s_i\bmod k\le\lfloor s_i/k\rfloor$。

设 $s_i=ak+r$。若 $r\le a$，取 $q_i=r,p_i=a-r$ 即得到合法表示。反之，任意表示可写为 $(p_i+q_i)k+q_i$；将 $q_i$ 对 $k$ 化简后仍需至少 $r$ 个 $k+1$，故 $r>a$ 时不可能。结论成立。

引理 2：算法对所有非整除 $x$ 的贡献计算正确。

由引理 1，不可表示条件在固定商 $k$ 时恰由算法列出的互不相交区间覆盖。前缀和准确统计其中的序列元素。整除分块枚举了所有具有该商的连续 $x$，并删除唯一可能的整除点，因此每个非整除 $x$ 被且仅被计算一次。

引理 3：算法对所有整除 $x$ 的贡献计算正确。

当 $x\mid N$ 时两个生成数均为 $k=N/x$，所以可表示性等价于 $k\mid s_i$。因为 $k\mid N$，又有 $k\mid s_i$ 当且仅当 $k\mid\gcd(s_i,N)$。算法正是按此条件汇总频次，故贡献正确。

定理：算法输出题目所求总和。

所有 $x\in[1,N]$ 恰分为整除与非整除两类。由引理 2、引理 3，两类贡献均被正确且不重不漏地计算，所以总和正确。

复杂度

每组测试的时间复杂度为 $O(N+n\log N)$，空间复杂度为 $O(N)$。利用所有测试的 $N$ 与 $n$ 之和限制，总复杂度满足要求。