题解

思路推导

从 $i$ 个不同元素中选出 $j$ 个并排成一个环，先排成线性序列再消去旋转的重复，可得

$$C(i,j)=\frac{i(i-1)\cdots(i-j+1)}{j}。$$

长度为 $j$ 的连续整数中恰有一个数在模 $j$ 意义下为 $0$。把这个数中的因子 $j$ 与分母约去后，其余 $j-1$ 个因子在模 $j$ 意义下恰为 $1,2,\ldots,j-1$，于是

$$C(i,j)\bmod j=\left((j-1)!\left\lfloor\frac{i}{j}\right\rfloor\right)\bmod j。$$

若 $j$ 是大于 $4$ 的合数，则 $(j-1)!$ 含有足够的质因子使其被 $j$ 整除；唯一的合数例外是 $j=4$。若 $j=p$ 为质数，由 Wilson 定理有 $(p-1)!\equiv-1\pmod p$。因此只有质数和 $4$ 会产生非零贡献。

做法

先用筛法求出不超过最大询问值的所有质数。对于每个质数 $p$，当 $i$ 位于区间 $[kp,(k+1)p-1]$ 时，它对当前内层和的贡献恒为

$$(-k)\bmod p=(p-(k\bmod p))\bmod p。$$

在差分数组上对这些整段区间做加法。$j=4$ 时的贡献为 $(2\lfloor i/4\rfloor)\bmod4$，同样按长度为 $4$ 的区间加入差分数组。

对差分数组做一次前缀和，可得每个 $i$ 的内层和；再做一次前缀和即可得到所有询问的答案。

正确性证明

上述约分说明，对任意 $i,j$，原式中的一项等于 $((j-1)!\lfloor i/j\rfloor)\bmod j$。合数阶乘整除性质和 Wilson 定理又说明，除质数与 $4$ 外的所有 $j$ 的贡献均为零，而算法对质数与 $4$ 计算的区间常值恰等于该式。因此第一次前缀和得到的正是固定 $i$ 的全部 $j$ 项之和。第二次前缀和把 $i=1$ 到询问值 $n$ 的这些内层和相加，故输出等于题目所求。

复杂度分析

设最大询问值为 $N$。筛法复杂度为 $O(N\log\log N)$；所有质数的分段更新总数为 $O(N\log\log N)$。总时间复杂度为 $O(N\log\log N+t)$，空间复杂度为 $O(N)$。