题解 P5746 【[NOI2002]机器人M号】

· · 题解

显然，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 号机器人并不在我们的讨论范围之内）。

#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;
}