題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 CF2053C Bewitching Stargazer

Problem Statement

題目簡述

有 $n$ 顆星排列在 $[1, n]$ 。Iris 觀察星星的遞迴過程如下：
對於當前區間 $[l, r]$ ，計算中間位置 $m = \lfloor \frac{l+r}{2} \rfloor$ 。

若區間長度 $len = r - l + 1$ 為偶數，則將其分為 $[l, m]$ 和 $[m+1, r]$ 兩個子區間繼續觀察。
若區間長度 $len$ 為奇數，則將 $m$ 加入幸運值，並將其分為 $[l, m-1]$ 和 $[m+1, r]$ 兩個子區間繼續觀察。
若區間長度小於 $k$ ，則停止觀察。

求最終的幸運值總和。

Constraints

約束條件

$1 \leq k \leq n \leq 2 \cdot 10^9$

思路：遞迴與對稱性 (Recursion & Symmetry)

由於 $n$ 可達 $2 \cdot 10^9$ ，我們不能直接模擬整個過程，必須尋找規律。

觀察：中心對稱性

關鍵觀察

觀察遞迴的分裂過程：

每次分裂時，區間被分為左右兩半（若為奇數長度則去掉中間點）。
對於原始區間 $[1, n]$ ，左半部分和右半部分的處理過程完全對稱。
任何被選中的位置 $m$ ，在對稱的另一側必有一個對應位置被選中。

這個對稱中心為 $\dfrac{n+1}{2}$ 。

由此可得：

核心性質

被選中的所有星星下標關於 $\dfrac{n+1}{2}$ 對稱。

若選中的星星總數為 $cnt$ ，則它們的總和為：

Ans = cnt \times \frac{n+1}{2}

計算選中數量 $cnt$

定義遞迴函數 dfs(len) 計算長度為 len 的區間會選中多少顆星：

終止條件：若 len < k，不再分裂，回傳 $0$ 。
遞迴步驟：
- 若 len 為偶數：分為兩段長度 $\lfloor \frac{len}{2} \rfloor$ 的區間，不選中任何星。
- 若 len 為奇數：中間點被選中 $(+1)$ ，再分為兩段長度 $\lfloor \frac{len}{2} \rfloor$ 的區間。

綜合起來，遞迴式為：

dfs(len) = \begin{cases} 0 & \text{if } len < k \\[6pt] 2 \cdot dfs\left(\left\lfloor \dfrac{len}{2} \right\rfloor\right) + (len \bmod 2) & \text{if } len \ge k \end{cases}

最終答案即為 $dfs(n) \times \dfrac{n+1}{2}$ 。

整數性保證

當 $n$ 為偶數時：選中的總數 $cnt$ 必為偶數（因偶數長度區間本身不選中任何點），因此 $cnt \times (n+1)$ 必能被 $2$ 整除。
當 $n$ 為奇數時： $(n+1)$ 為偶數，因此 $cnt \times (n+1)$ 必能被 $2$ 整除。

綜上，無論 $n$ 奇偶，計算結果皆為整數。

複雜度分析

時間複雜度： $\mathcal{O}(\log n)$ ，每次遞迴長度減半，深度為 $\log n$ 。
空間複雜度： $\mathcal{O}(\log n)$ ，遞迴堆疊深度。

Code

def solve():
    n, k = map(int, input().split())

    def dfs(ln):
        if ln < k:
            return 0
        return 2 * dfs(ln // 2) + (ln & 1)
    print(dfs(n) * (n + 1) // 2)

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

寫在最後

PROMPT

這裡什麼都沒有。