HDU 5670：Machine——三進制規律與燈泡顏色變換

題目大意

m（2≤m≤30）個燈泡初始全紅(R)。按鈕一次：最右燈泡變色（R→G→B→R），若由B變R則觸發左鄰燈泡同樣變色（進位）。求按n（1≤n<2^63）次後燈泡顏色序列。

核心規律：三進制計數器

每個燈泡狀態對應三進制一位：R=0, G=1, B=2。
按鈕一次 = 三進制數加1。
最右燈泡 = 最低位，每次加1必變。
第i個燈泡（從右數，0-indexed）每3^i次變化一次。
最終狀態 = n的三進制表示，低位對應右燈泡，高位補0對應左燈泡。

算法

1. 預計算pow3[i] = 3^i（i=0..m-1，用unsigned long long或__int128防溢出）。
2. 對每個燈泡i（從左到右，即高位到低位）：
   • times = n / pow3[m-1-i]（該位經歷的完整輪數）。
   • state = times % 3（0=R, 1=G, 2=B）。
3. 輸出顏色字符串。

參考代碼 (C++)

樣例驗證

m=3, n=1：n=1 (三進制001) → 燈泡狀態 0,0,1 → R R G ✓
m=2, n=3：n=3 (三進制10) → 燈泡狀態 1,0 → G R ✓


總結
本題是進位制轉換的直觀應用。識別出「按鈕=加1、燈泡=三進制位、進位規則=B→R觸發左鄰」的對應關係，即可用O(m)時間直接計算第n步狀態，無需模擬。注意n<2^63需用64位無符號整數存儲3^30（≈2e14）及中間計算。