题意

对于机器人m，
老师：m的因子
独立数：所有编号比它小且与它知识互相独立的机器人的个数，即欧拉函数
政客：能分解成偶数个不同奇素数的积
军人：能分解成奇数个不同奇素数的积
学者：其他

求机器人m和它的老师中，所有政客的独立数之和，所有军人的独立数之和，以及所有学者的独立数之和模10000。

输入及输出

【输入】

输入文件robot.in的第一行是一个正整数k(1<=k<=1000)，k是m的不同的素因子个数。

以下k行，每行两个整数，pi, ei,表示m的第i个素因子和它的指数(i = 1, 2, …, k)。p1, p2, …, pk是不同的素数，。所有素因子按照从小到大排列，即p1<p2<…<pk。输入文件中，2<=pi<10,000, 1<=ei<=1,000,000。

【输出文件】

输出文件robot.out包括三行。
第一行是机器人m号和它的老师中，所有政客的独立数之和除以10000的余数。
第二行是机器人m号和它的老师中，所有军人的独立数之和除以10000的余数。
第三行是机器人m号和它的老师中，所有学者的独立数之和除以10000的余数。

【样例输入】

3
2 1
3 2
5 1

【样例输出】

8
6
75

【样例说明】

90号机器人有10个老师，加上它自己共11个。其中政客只有15号；军人有3号和5号；学者有8个，它们的编号分别是：2,6,9,10,18,30,45,90。

题解

一条蜜汁定理：一个数所有因子欧拉函数之和等于这个数-1.
因此只要求出政客数和军人数，剩下的就是学者数。
考虑欧拉函数性质 $phi(i j)=phi(i) phi(j)$
设dp[i][j]为前i个因数里面选了j个的欧拉函数和，则有转移方程：

$dp[i][j]=dp[i-1][j]+dp[i-1][j-1]* (p[i]-1)$

（p[i]为第i个因数）
注：前i-1个因数里面选j个，或前i-1个因数里面选j-1个，并选了第i个因数
然后分别求k个因数里面选奇数个和偶数个因数的和即可。
用快速幂取模求m，则所有因数的欧拉函数和为m-1

#include <bits/stdc++.h>
using namespace std;

int p[1005];
int e[1005];
int dp[1005][1005];
int mod=10000;

int qpow(int num,int x){
    int ans=1;
    while(x){
        if(x&1) ans=ans*num%mod;
        num=(num%mod)*(num%mod)%mod;
        x>>=1;
    }
    return ans%mod;
}

int main(){
    int k;scanf("%d",&k);
    int m=1;
    for(int i=1;i<=k;i++){
        scanf("%d%d",&p[i],&e[i]);
        m=m*qpow(p[i],e[i])%mod;
    }
    int cnt=1;
    if(p[cnt]==2) cnt++;
    for(int i=cnt;i<=k;i++) dp[i][cnt]=dp[i-1][cnt]+p[i]-1;
    for(int i=cnt+1;i<=k;i++){
        for(int j=cnt+1;j<=k;j++)
            dp[i][j]=(dp[i-1][j]+dp[i-1][j-1]*(p[i]-1)%mod)%mod;
    }
    int sum1=0,sum2=0;
    for(int i=1;i<=k;i++){
        if(i&1) sum1+=dp[k][i],sum1%=mod;
        else sum2+=dp[k][i],sum2%=mod;
    }
    int sum3=((m-sum1+mod)%mod-sum2+mod-1)%mod;
    printf("%d\n%d\n%d\n",sum1,sum2,sum3);
    return 0;
}