题目理解

定义 $C(i,k)$ 为从集合 $\{1,2,\dots,i\}$ 中选出 $k$ 个不同的数，并排成一个圆环（旋转视为相同）的不同方式数。

需要计算： $ S(n) = \sum_{i=1}^n \sum_{j=1}^i \big(C(i,j) \bmod j\big) $ 对 $10^9+7$ 取模。

---

1. 推导 $C(i,j)$ 的公式

• 先从 $i$ 个数中选 $k$ 个：$\binom{i}{k}$ 种选法。
• 将选出的 $k$ 个数排成圆环：$(k-1)!$ 种排列（固定一个位置消除旋转）。

因此： $ C(i,k) = \binom{i}{k} \cdot (k-1)! = \frac{i!}{k \cdot (i-k)!} $

展开为： $C(i,j) = \frac{i(i-1)\cdots(i-j+1)}{j}$

分子是 $j$ 个连续整数的乘积。

---

2. 化简 $C(i,j) \bmod j$

因为分子是 $j$ 个连续整数，其中必有一个是 $j$ 的倍数。具体来说，这个倍数是： $j \times \left\lfloor \frac{i}{j} \right\rfloor$

从分子中除去分母 $j$ 后，该因子变成 $\left\lfloor \frac{i}{j} \right\rfloor$，而剩下的 $j-1$ 个因子模 $j$ 后恰好覆盖 $1,2,\dots,j-1$ 各一次。

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

---

3. 分情况讨论

情况 1：$j$ 是素数且 $j \neq 2$

根据威尔逊定理，当 $j$ 是素数时： $(j-1)! \equiv -1 \pmod{j}$ 所以： $ C(i,j) \bmod j \equiv -\left\lfloor \frac{i}{j} \right\rfloor \pmod{j} $

情况 2：$j$ 是合数

对于合数 $j$，$(j-1)!$ 包含 $j$ 的所有真因子，因此 $(j-1)! \equiv 0 \pmod{j}$，所以： $C(i,j) \bmod j = 0$

但有一个特例：$j=4$
$(4-1)! = 6 \equiv 2 \pmod{4}$，不是 $0$，需要单独处理。

对于 $j=4$： $ C(i,4) \bmod 4 = \left( 2 \times \left\lfloor \frac{i}{4} \right\rfloor \right) \bmod 4 $

---

4. 算法思路

我们需要计算： $ S(n) = \sum_{i=1}^n \sum_{j=1}^i \left[ C(i,j) \bmod j \right] $

直接双重循环不可行，因为 $n$ 可达 $10^6$，$t$ 可达 $10^5$。

关键技巧：交换求和顺序

我们考虑所有满足 $j \le i$ 的数对 $(i,j)$，贡献为 $C(i,j) \bmod j$。
固定 $j$，考虑所有 $i \ge j$ 的贡献。

对于每个 $j$：

• 如果 $j$ 是合数且 $j \neq 4$，贡献为 $0$。
• 如果 $j$ 是素数，贡献为 $-\lfloor i/j \rfloor \bmod j$。
• 如果 $j=4$，贡献为 $2\lfloor i/4 \rfloor \bmod 4$。

因此，只有素数（和 $4$）需要处理。

---

5. 使用差分数组优化

对于素数 $p$，我们要计算： $ \sum_{i=1}^n \sum_{j=1}^i [j=p] \cdot \left( -\left\lfloor \frac{i}{p} \right\rfloor \bmod p \right) $

设 $i = qp + r$，其中 $0 \le r < p$，则 $\lfloor i/p \rfloor = q$，贡献为 $(-q) \bmod p = p - (q \bmod p)$（当 $q \bmod p \neq 0$ 时）或 $0$（当 $q \bmod p = 0$ 时）。

具体地，对于固定的 $p$，考虑区间 $[kp, (k+1)p - 1]$ 内的所有 $i$，都有 $\lfloor i/p \rfloor = k$，贡献为 $(-k) \bmod p$。

我们可以用差分数组 del 来累加这些贡献：

• 在 $i = kp$ 处加上 $(-k) \bmod p$
• 在 $i = (k+1)p$ 处减去 $(-k) \bmod p$

这样，对 del 做前缀和，就能得到每个 $i$ 处所有素数的贡献之和。

对于 $p=4$ 同理处理。

---

6. 最终计算

• 预处理所有素数（用埃氏筛）。
• 对每个素数 $p$，更新差分数组 del。
• 对 $p=4$ 单独更新。
• 对 del 做前缀和，得到每个 $i$ 的贡献 $f(i) = \sum_{j \le i} (C(i,j) \bmod j)$。
• 再对 $f(i)$ 做前缀和，得到 $S(n) = \sum_{i=1}^n f(i)$。
• 输出 $S(n) \bmod 10^9+7$。

---

7. 复杂度分析

• 埃氏筛：$O(n \log \log n)$
• 更新素数：每个素数 $p$ 的循环次数约为 $n/p$，总和 $O(n \log \log n)$
• 总复杂度 $O(n \log \log n)$，可以处理 $n=10^6$。

---

8. 代码对应解析

// 预处理素数
primes = eratosthenesSieve(MAX_N);
vector<int> del(MAX_N, 0);

// 处理所有素数 p
for (auto &p: primes) {
    for (int curr = p; curr < MAX_N; curr += p) {
        int inc = (p - ((curr / p) % p)) % p;  // (-k) mod p
        del[curr] = (del[curr] + inc) % MOD;
        if (curr + p < MAX_N) 
            del[curr + p] = (del[curr + p] - inc + MOD) % MOD;
    }
}

// 处理 j = 4 的特例
for (int curr = 4; curr < MAX_N; curr += 4) {
    int inc = (2 * (curr / 4)) % 4;  // 2 * floor(i/4) mod 4
    del[curr] = (del[curr] + inc) % MOD;
    if (curr + 4 < MAX_N) 
        del[curr + 4] = (del[curr + 4] - inc + MOD) % MOD;
}

// 前缀和得到 f(i) 和 S(n)
int pref = 0;
for (int i = 1; i < MAX_N; i++) {
    pref = (pref + del[i]) % MOD;     // f(i)
    ans[i] = (ans[i - 1] + pref) % MOD; // S(i)
}

---

9. 示例验证

以 $n=3$ 为例：

• 素数 $p=2$：$i=2$ 贡献 $(-1) \bmod 2 = 1$，$i=3$ 贡献 $(-1) \bmod 2 = 1$
• 素数 $p=3$：$i=3$ 贡献 $(-1) \bmod 3 = 2$
• 合计 $f(1)=0$, $f(2)=1$, $f(3)=1+2=3$
• $S(3)=0+1+3=4$，与样例一致。

---

这样，我们就得到了一个高效的 $O(n \log \log n)$ 解法。