Virtual Participation 時花了 40 分鐘沒能搞定的題
不過當時有正確的大方向 (枚舉)
題意：
將一個正整數 X 表示為 n-bit 的 binary-string, S
不可以有前置零 (leading zeros)
若果存在 長度為 k < n 的 循環節 (period)
(i.e., 使得 S[i+k] = S[i] for 0 <= i < n-k)
則稱 X 為 periodical
給定區間 [L, R], 問當中有多少個 periodical 的正整數
(題目連結)
思路：
先把問題簡化為
求 [1, R] 當中 periodical 正整數的個數
(那麼最後答案 := DOIT(R) - DOIT(L-1))
對於 循環節 長度為 k 的 X，可以將 X 表示成：
- X = Y × (00...01 00...01 00...01 ... 00...01) (二進制表示及計算，下同)
- (00...01 00...01 00...01 ... 00...01) 是 m-bit 二進位數，其中 m <= n
- 每一個 00...01 是 k-bit 二進位數
