杂题选做
目录
- P5746 [NOI2002] 机器人M号
P5746 [NOI2002] 机器人M号
传送门
有DP解法和数学解法。
DP解法显然，设 \(f[i][j](j \in \left \{ 0,1 \right \})\) 表示前 \(i\) 个素数中，选了奇/偶数个因子的独立数的和，则易得方程 \(f[i][j]=f[i-1][j \otimes 1]\times\varphi(p_i)+f[i-1][j]\) 。
数学解法还没看懂。
传送门
有DP解法和数学解法。
DP解法显然，设 \(f[i][j](j \in \left \{ 0,1 \right \})\) 表示前 \(i\) 个素数中，选了奇/偶数个因子的独立数的和，则易得方程 \(f[i][j]=f[i-1][j \otimes 1]\times\varphi(p_i)+f[i-1][j]\) 。
数学解法还没看懂。