BestCoder Round #81 (Div.2) 1001 Machine：三進制規律求燈光顏色

題目大意

有 M 盞燈，初始全為紅色（R）。每次操作將第一盞燈按 R→G→B→R 循環變色；若第一盞燈由 B 變為 R，則觸發第二盞燈變色，以此類推（類似進位）。進行 N 次操作後，輸出每盞燈的顏色。M ≤ 38，N 為 64 位整數。

解題思路：三進制表示

觀察可知：第 1 盞燈每 1 次操作變色（週期 3），第 2 盞每 3 次（週期 9），第 i 盞每 3^{i-1} 次。這正是 三進制計數器的行為！將 N 轉為三進制，第 i 位（從低到高）即為第 i 盞燈的變色次數模 3：

• 0 → R（紅）
• 1 → G（綠）
• 2 → B（藍）

只需將 N 反覆除以 3 取餘，填入陣列 d[1..M]，最後按順序輸出對應顏色字符。

參考代碼 (C++)

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; cin >> T;
    while (T--) {
        int M; long long N;
        cin >> M >> N;
        int d[40] = {0};
        for (int i = M; i >= 1; --i) {
            d[i] = N % 3;
            N /= 3;
        }
        for (int i = 1; i <= M; ++i) {
            if (d[i] == 0) cout << 'R';
            else if (d[i] == 1) cout << 'G';
            else cout << 'B';
        }
        cout << '\n';
    }
    return 0;
}

核心洞察

將「連續操作引發的連鎖進位」建模為 進位制計數，是解決此類「多狀態循環觸發」問題的通用技巧。同理可擴展至 K 進制、不同初始狀態等變體。