P5746 [NOI2002]机器人M号

解题思路

首先一个机器人m的独立数是$φ(m)φ(m)$而老师的数量就是他的因数数量-2，然后把M分解为

$p1e1×p2e2×p3e3...×pkek$

然后

$φ(m)$=$p1e1×p2e2...×pkek×(1−1p1)×(1−1p2)...× (1−1pk)$

之后

$φ(m)$=$(p1−1)p1e1−1×(p2−1)p2e2−1...×(pk−1) pkek−1$

然后我们就可以发现政客的独立数就是在M的奇质因数中选择偶数个不同的乘起来的欧拉函数，军人就是选奇数个。然后学者就是Ｍ所以的独立数减去政客和军人。

选数我们可以用dp

$f[i mod 2][0]$表示在M因子中只包含前$i$个的政客的欧拉函数

$f[i mod 2][1]$表示在M因子中只包含前$i$个的政客的欧拉函数

然后进行动态转移

$f[i mod 2][0]=f[(i+1) mod 2][0]+f[(i+1) mod 2][1]∗(p−1)$

$f[i mod 2][1]=f[(i+1) mod 2][1]+f[(i+1) mod 2][0]∗(p−1)$

最后计算$φ(m)φ(m)$减去最后的政客独立数总和和军人独立数总和

#include<cstdio>
#define mods 10000
using namespace std;
int n,p,e,f[2][2],m=1;
int ksm(int x,int k)//快速幂
{
    int ans=1;
    while (k)
    {
        if (k&1) ans=(ans*x)%mods;
        x=x*x%mods;
        k/=2;
    }
    return ans;
}
int main()
{
    scanf("%d",&n);
    scanf("%d%d",&p,&e);
    m=m*ksm(p,e)%mods;
    if (p==2) f[1][0]=1;
    else
    {
        f[0][0]=1;
        f[1][0]=(f[0][0]+f[0][1]*(p-1)%mods)%mods;
        f[1][1]=(f[0][1]+f[0][0]*(p-1)%mods)%mods;
    }//初始化
    for (int i=2;i<=n;i++)
    {
        scanf("%d%d",&p,&e);
        m=m*ksm(p,e)%mods;
        f[i&1][0]=(f[~-i&1][0]+f[~-i&1][1]*(p-1)%mods)%mods;
        f[i&1][1]=(f[~-i&1][1]+f[~-i&1][0]*(p-1)%mods)%mods;
        //动态转移
    }
    f[n&1][0]--;m=((m-1-f[n&1][0]-f[n&1][1])%mods+mods)%mods;//计算学者
    printf("%d\n%d\n%d",f[n&1][0],f[n&1][1],m);
}