自动搬运

查看原文

来自洛谷，原作者为

	StudyingFather 在纷繁杂乱的世界里，独自寻找属于自己的光荣与梦想。

搬运于2025-08-24 22:13:59，当前版本为作者最后更新于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$ 号机器人并不在我们的讨论范围之内）。

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