Description
Input
Output
Sample Input
3
2 1
3 2
5 1
2 1
3 2
5 1
Sample Output
8
6
75
6
75
HINT
90号机器人有10个老师，加上它自己共11个。其中政客只有15号；军人有3号和5号；学者有8个，它们的编号分别是：2,6,9,10,18,30,45,90。
$\sum\limits_{d|n}\phi(d)=n$
因此总和为n。
只需要求约数中$\mu$为1的$\varphi$和，$\mu$为-1的$\varphi$和。
这样，我们每个质因子只有一次贡献。
这次贡献会把之前的$\mu$从1变到-1，从-1变到1。
又因为phi是积性函数，每次都需要乘上$\varphi(p)=p-1$。
要注意2不是奇质数。一个数的约数不考虑1。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
#define mod 10000
int n,m,p,k,f[1050],g[1050];
int qp(int x,int y) {
int re=1;
while(y) {
if(y&1) re=re*x%mod;
x=x*x%mod;
y>>=1;
}
return re;
}
int main() {
scanf("%d",&n);
m=1;
int i;
f[0]=1;
for(i=1;i<=n;i++) {
scanf("%d%d",&p,&k); m=m*qp(p,k)%mod;
if(p!=2) {
f[i]=(f[i-1]+g[i-1]*(p-1)%mod)%mod;
g[i]=(g[i-1]+f[i-1]*(p-1)%mod)%mod;
}else {
f[i]=f[i-1];
g[i]=g[i-1];
}
}
f[n]=(f[n]-1+mod)%mod;
printf("%d\n%d\n%d\n",f[n],g[n],((m-f[n]-g[n]-1)%mod+mod)%mod);
}