📐 Math & Geometry
數學性質與幾何模擬。
23 題
📖 分類導讀
結合數學推理和幾何性質來解題。包含模運算、矩陣操作、座標幾何等主題。
Notes:
- 矩陣旋轉和螺旋遍歷是常見的面試題
- 數學題常需要找規律或利用數論性質
- 注意整數溢位問題
常用數論工具
- 最大公因數 (GCD)：歐幾里得輾轉相除，
gcd(a, b) = gcd(b, a % b)；最小公倍數lcm(a, b) = a / gcd(a, b) * b（先除再乘避免溢位）。 - 模運算：
(a + b) % m、(a * b) % m可逐步取模避免中途溢位；題目常要求對1e9 + 7取模。注意負數取模在 Kotlin 會得到負值，需((x % m) + m) % m修正。 - 質數：判質只需試到
sqrt(n)；要一次篩出範圍內所有質數用埃拉托斯特尼篩法O(n log log n)。
fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)常見公式
| 場景 | 公式 |
|---|---|
| 1 加到 n | n * (n + 1) / 2 |
等比和 1 + 2 + 4 + ... + 2^k | 2^(k+1) - 1 |
| n 個元素的排列數 | n! |
| 從 n 取 k 的組合數 | n! / (k! * (n - k)!) |
WARNING
整數溢位是數學題最常見的坑：先估算中間值的量級，必要時改用 Long，或在運算中提前取模／改寫式子（如「先除再乘」）。
浮點數比較不要用 ==，改判斷 abs(a - b) < 1e-9；幾何題盡量用整數運算（如用叉積判方向）以避開精度誤差。