题解 P5746 【[NOI2002]机器人M号】
StudyingFather
2019-12-08 14:00:17
显然，$i$ 号机器人的独立数就是 $\varphi(i)$（特别地，$1$ 号机器人的独立数为 $0$）。
政客和军人的独立数之和可以很容易用 DP 求出。
设 $f(i,0/1)$ 表示前 $i$ 个因子中，选了奇数个或偶数个因子的独立数的和。
对于当前因子有选和不选两种决策，所以有，
$$
f(i,j)=f(i-1,j \oplus 1) \times \varphi(p_i) + f(i-1,j)
$$
（别忘了 $p_i$ 都是质数，所以$\varphi(p_i)=p_i-1$）
特别地，因为政客和军人的讨论范围都是奇素数，因此要对 $p_i=2$ 的情况特殊处理。
最后用总独立数减去政客和军人的独立数即可得到学者的独立数。
总独立数并不难算，因为 $m= \sum_{d|m} \varphi(d)$，故总独立数为 $m-1$（别忘了 $1$ 号机器人并不在我们的讨论范围之内）。
```cpp
#include <cstdio>
#define MOD 10000
int f[1005][2];
int fpow(int x,int y)
{
int ans=1;
while(y)
{
if(y&1)ans=ans*x%MOD;
x=x*x%MOD;
y>>=1;
}
return ans;
}
int main()
{
int k;
scanf("%d",&k);
int tot=1;
f[0][0]=1;
for(int i=1;i<=k;i++)
{
int p,e;
scanf("%d%d",&p,&e);
tot=tot*fpow(p,e)%MOD;
for(int j=0;j<=1;j++)
f[i][j]=(f[i-1][j^1]*(p==2?0:p-1)+f[i-1][j])%MOD;
}
f[k][0]=(f[k][0]-1+MOD)%MOD;
printf("%d\n",f[k][0]);
printf("%d\n",f[k][1]);
printf("%d\n",((tot-f[k][0]-f[k][1]-1)%MOD+MOD)%MOD);
return 0;
}
```