机器人M号问题：数论与动态规划的C++实现

1. 机器人M号问题解析与C++实现

今天我们来拆解一道经典的NOI2002题目——机器人M号。这道题融合了数论、动态规划和组合数学等多个知识点，非常适合用来锻炼算法思维。下面我会从题目分析、数学推导到代码实现，一步步带你攻克这个难题。

1.1 题目背景与核心概念

题目描述了一个机器人繁殖系统：

• 1号机器人是始祖，每秒产生一个新机器人（第m秒产生m号机器人）
• m号机器人每m秒休息一次，休息时会将记忆复制给当时出生的机器人
• 知识独立定义：没有师徒关系且没有共同老师的机器人互为知识独立
• 独立数：比当前机器人编号小且知识独立的机器人数量

机器人职业分类规则：

1. 政客：编号能分解为偶数个不同奇素数的乘积（如15=3×5）
2. 军人：编号是奇素数或能分解为奇数个不同奇素数的乘积（如3, 165=3×5×11）
3. 学者：其他情况（如2,6,9）

1.2 问题转化与数学建模

经过分析，我们可以将问题转化为：

1. 找出m的所有因数（老师和m自己）
2. 对每个因数判断其职业类型
3. 计算每个因数的独立数
4. 按职业分类统计独立数之和

关键在于独立数的计算。通过观察可以发现：

• 独立数实际就是欧拉函数φ(m)的值
• 对于m的因数d，其独立数为φ(d)
• 特别地，1号的独立数为0

欧拉函数φ(n)表示小于n且与n互质的正整数个数。对于n=p₁^e₁×p₂^e₂×...×p_k^e_k，有：
φ(n) = n × ∏(1 - 1/p_i)

2.1 动态规划解法设计

直接计算所有因数的欧拉函数再分类求和效率太低（当m很大时）。我们需要更聪明的方法：

定义f[i][j]表示考虑前i个素因子，选取奇数(j=1)或偶数(j=0)个奇素数的乘积对应的欧拉函数和。

状态转移方程：
f[i][j] = f[i-1][j^1] × (p_i == 2 ? 0 : φ(p_i)) + f[i-1][j]

其中：

• 当p_i=2时不影响奇偶性（因为2不是奇素数）
• 对于奇素数p_i，φ(p_i)=p_i-1

最终结果：

• 政客和：f[k][0] - 1（减去1号机器人）
• 军人和：f[k][1]
• 学者和：总数 - 政客和 - 军人和 - 1（1号）

2.2 关键代码实现解析

cpp复制