BZOJ 1408 NOI2002 機器人：數論解法詳解

題目背景

BZOJ 1408（NOI 2002 機器人）是一道經典的數論題目。題目定義了變形的歐拉函數 φ 和莫比烏斯函數 μ：φ(1)=0，μ 僅計算奇質數，含有因子 2 的數 μ 值視為 0。目標是求解三個子問題，最終答案可由總答案減去前兩問得到。

核心思路

1. μ 函數的性質

根據新定義，μ(n) ≠ 0 當且僅當 n 的所有質因數次數均為 1（即 n 為無平方因子數），且不含因子 2。因此我們只需枚舉奇質數，計算加入該質數後 φ 值之和的增量。

2. φ 函數的積性

φ 是積性函數，利用此性質可在 O(n) 時間內解出前兩問。具體做法是動態維護答案：對每個奇質數 p，更新 ans1 和 ans2，公式為：

temp1 = (ans1 + ans2 * (p-1)) % MOD
temp2 = (ans2 + (ans1+1) * (p-1)) % MOD

3. 總答案與第三問

利用恆等式 Σ_{d|n} φ(d) = n，總答案為 m-1（因題目 1 不算作其他數的因子，故去掉 1）。第三問答案即 (m-1) - ans1 - ans2（取模調整）。

代碼實現要點

• 快速冪計算 m = ∏ p_i^{a_i} (mod MOD)。
• 輸入質因子分解，跳過 p=2。
• 最終輸出三個答案。

複雜度分析

時間複雜度 O(n + log MOD)，空間 O(1)，極其高效。

總結

本題巧妙結合數論函數變形與積性函數性質，通過動態規劃式的累加快速得出答案，是數論競賽題中的佳作。