在 LaTeX/Markdown 中，分段函数（`cases`）的换行需要使用双反斜杠 `\\`。如果直接在正文中排版，有时会被 Markdown 解析器错误地过滤掉一个反斜杠。

为了保证清晰的展现，这里使用**独立公式块**将其重新排版，并附上该分治公式的推导逻辑，方便您理解：

### 等比数列模意义下求和的分治公式

设等比数列的前 $n$ 项和为：
$$S\_n = a\_1 + a\_1q + a\_1q^2 + \dots + a\_1q^{n-1}$$

当项数 $n$ 较大且模数与公比不互质时，我们可以使用以下分治公式在 $O(\log n)$ 时间复杂度内求出 $S\_n$：

$$
S\_n = 
\begin{cases} 
a\_1 & n = 1 \\ 
(1 + q^{n/2}) S\_{n/2} & n \text{ 为偶数} \\ 
(1 + q^{(n-1)/2}) S\_{(n-1)/2} + a\_1 q^{n-1} & n \text{ 为奇数} 
\end{cases}
$$

---

### 公式推导过程

#### 1. 当 $n$ 为偶数时（设 $n = 2k$）
我们将前 $2k$ 项平分成左右两部分：
$$
\begin{aligned}
S\_{2k} &= \underbrace{(a\_1 + a\_1q + \dots + a\_1q^{k-1})}\_{\text{前 } k \text{ 项}} + \underbrace{(a\_1q^k + a\_1q^{k+1} + \dots + a\_1q^{2k-1})}\_{\text{后 } k \text{ 项}} \\
&= S\_k + q^k(a\_1 + a\_1q + \dots + a\_1q^{k-1}) \\
&= S\_k + q^k S\_k \\
&= (1 + q^k) S\_k
\end{aligned}
$$
由于 $k = n/2$，代入即得：
$$S\_n = (1 + q^{n/2}) S\_{n/2}$$

#### 2. 当 $n$ 为奇数时（设 $n = 2k + 1$）
我们可以先求前 $2k$ 项的和（偶数项，直接套用上面的结论），再加上最后一项：
$$
\begin{aligned}
S\_{2k+1} &= S\_{2k} + a\_1q^{2k} \\
&= (1 + q^k) S\_k + a\_1q^{2k}
\end{aligned}
$$
由于 $k = (n-1)/2$，且最后一项的幂次 $2k = n-1$，代入即得：
$$S\_n = (1 + q^{(n-1)/2}) S\_{(n-1)/2} + a\_1 q^{n-1}$$

---

### 实现该算法的 C++ 示例代码

在编程时，我们可以递归调用此过程。由于计算中包含 $q^k$，可以使用**快速幂**进行辅助计算。

```cpp
// 快速幂：计算 base^exp % MOD
long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

// 分治法求等比数列前 n 项和：% mod
long long get_geometric_sum(long long a1, long long q, long long n, long long mod) {
    if (n == 1) return a1 % mod;
    
    if (n % 2 == 0) {
        long long half_sum = get_geometric_sum(a1, q, n / 2, mod);
        long long q_pow_half = power(q, n / 2, mod);
        return half_sum * (1 + q_pow_half) % mod;
    } else {
        long long half_sum = get_geometric_sum(a1, q, (n - 1) / 2, mod);
        long long q_pow_half = power(q, (n - 1) / 2, mod);
        long long last_term = a1 * power(q, n - 1, mod) % mod;
        return (half_sum * (1 + q_pow_half) % mod + last_term) % mod;
    }
}
```

在 LaTeX/Markdown 中，分段函数（cases）的换行需要使用双反斜杠 \\。如果直接在正文中排版，有时会被 Markdown 解析器错误地过滤掉一个反斜杠。

为了保证清晰的展现，这里使用独立公式块将其重新排版，并附上该分治公式的推导逻辑，方便您理解：

等比数列模意义下求和的分治公式

设等比数列的前 $n$ 项和为： $$S_n = a_1 + a_1q + a_1q^2 + \dots + a_1q^{n-1}$$

当项数 $n$ 较大且模数与公比不互质时，我们可以使用以下分治公式在 $O(\log n)$ 时间复杂度内求出 $S_n$：

$$ S_n = \begin{cases} a_1 & n = 1 \ (1 + q^{n/2}) S_{n/2} & n \text{ 为偶数} \ (1 + q^{(n-1)/2}) S_{(n-1)/2} + a_1 q^{n-1} & n \text{ 为奇数} \end{cases} $$

公式推导过程

1. 当 $n$ 为偶数时（设 $n = 2k$）

我们将前 $2k$ 项平分成左右两部分： $$ \begin{aligned} S_{2k} &= \underbrace{(a_1 + a_1q + \dots + a_1q^{k-1})}_{\text{前 } k \text{ 项}} + \underbrace{(a_1q^k + a_1q^{k+1} + \dots + a_1q^{2k-1})}_{\text{后 } k \text{ 项}} \ &= S_k + q^k(a_1 + a_1q + \dots + a_1q^{k-1}) \ &= S_k + q^k S_k \ &= (1 + q^k) S_k \end{aligned} $$ 由于 $k = n/2$，代入即得： $$S_n = (1 + q^{n/2}) S_{n/2}$$

2. 当 $n$ 为奇数时（设 $n = 2k + 1$）

我们可以先求前 $2k$ 项的和（偶数项，直接套用上面的结论），再加上最后一项： $$ \begin{aligned} S_{2k+1} &= S_{2k} + a_1q^{2k} \ &= (1 + q^k) S_k + a_1q^{2k} \end{aligned} $$ 由于 $k = (n-1)/2$，且最后一项的幂次 $2k = n-1$，代入即得： $$S_n = (1 + q^{(n-1)/2}) S_{(n-1)/2} + a_1 q^{n-1}$$

实现该算法的 C++ 示例代码

在编程时，我们可以递归调用此过程。由于计算中包含 $q^k$，可以使用快速幂进行辅助计算。

// 快速幂：计算 base^exp % MOD
long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

// 分治法求等比数列前 n 项和：% mod
long long get_geometric_sum(long long a1, long long q, long long n, long long mod) {
    if (n == 1) return a1 % mod;

    if (n % 2 == 0) {
        long long half_sum = get_geometric_sum(a1, q, n / 2, mod);
        long long q_pow_half = power(q, n / 2, mod);
        return half_sum * (1 + q_pow_half) % mod;
    } else {
        long long half_sum = get_geometric_sum(a1, q, (n - 1) / 2, mod);
        long long q_pow_half = power(q, (n - 1) / 2, mod);
        long long last_term = a1 * power(q, n - 1, mod) % mod;
        return (half_sum * (1 + q_pow_half) % mod + last_term) % mod;
    }
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com