🚀 ダブリング法による数字操作問題
詳細アルゴリズム解析

function getDigitSum(n: number): number { let sum = 0; while (n > 0) { sum += n % 10; // 最下位桁を取得 n = Math.floor(n / 10); // 桁を右シフト } return sum; } // 例: getDigitSum(123) → 1+2+3 = 6 // 計算量: O(log₁₀ n) ≈ 桁数に比例

// bit=1の構築例（2回操作） for (let i = 0; i <= maxIndex; i++) { table[1][i] = table[0][table[0][i]]; // i → 1回操作 → 1回操作 = 2回操作 } // bit=2の構築例（4回操作） for (let i = 0; i <= maxIndex; i++) { table[2][i] = table[1][table[1][i]]; // i → 2回操作 → 2回操作 = 4回操作 }

// K=13 (1101₂) の場合 function queryExample(start: number) { let current = start; // ビット0が立っている → 1回操作 if (13 & 1) current = table[0][current]; // ビット2が立っている → 4回操作 if (13 & 4) current = table[2][current]; // ビット3が立っている → 8回操作 if (13 & 8) current = table[3][current]; return current; // 合計13回操作後の値 }