NOI 2002 机器人M号
该问题的数学模型是数论问题.机器人M号的所有老师就是小于M大于1M的所有约数,M号机器人的独立数就是小于M于M互质的数的个数,即为M的欧拉函数φ(M).
把M分解为P1^e1P2^e2...*Pk^ek,欧拉函数有公式为
φ(M)=(P1-1)*P1^(e1-1) * (P2-1)*P2^(e2-1) * ... * (Pk-1)*Pk^(ek-1)
于是所有"政客"的独立数之和就是M的奇质因数中选出偶数个不同的质因数乘积的欧拉函数值之和,"军人"则是选出奇数个."学者"无法直接 算出,然我们知道除了"政客"和"军人"就是学者,只需用小于M的M的所有约数的独立数之和减去"政客"和"军人"的独立数