记录编号	60292	评测结果	AAAAAAAAAA
题目名称	[NOI 2002]机器人M号	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.040 s
提交时间	2013-05-21 20:02:54	内存使用	0.26 MiB

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<map>
#include<set>
#include<vector>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int SIZEN=1001,MOD=10000;
int n;//也就是k了,素因子个数
int p[SIZEN]={0},e[SIZEN]={0};//素因子和指数
//下标从1开始
int allf=0;//=all φ
int polf=0,solf=0,schf=0;//政客,军人,学者,前两者分别对应偶数/奇数个不同奇素数乘积
void calc_other(void){
	int f[SIZEN][2]={0};
	f[0][0]=1;
	int i;
	for(i=1;i<=n;i++){
		if(p[i]==2){
			f[i][0]=f[i-1][0],f[i][1]=f[i-1][1];
			continue;
		}
		f[i][0]=f[i-1][0];
		f[i][0]+=f[i-1][1]*(p[i]-1);
		f[i][0]%=MOD;
		f[i][1]=f[i-1][1];
		f[i][1]+=f[i-1][0]*(p[i]-1);
		f[i][1]%=MOD;
	}
	polf=f[n][0],solf=f[n][1];
	polf=((polf-1)%MOD+MOD)%MOD;
	schf=((allf-polf-solf)%MOD+MOD)%MOD;
}
int quickpow(int a,int x){//a^x对MOD取模
	int temp=a,ans=1;
	while(x){
		if(x&1)	ans=ans*temp%MOD;
		temp=temp*temp%MOD;
		x>>=1;
	}
	return ans;
}
void calc_all(void){
	int ans=1;
	int i;
	for(i=1;i<=n;i++) ans=ans*quickpow(p[i],e[i])%MOD;
	ans--;
	allf=(ans%MOD+MOD)%MOD;
}
void read(void){
	scanf("%d",&n);
	int i;
	for(i=1;i<=n;i++) scanf("%d%d",&p[i],&e[i]);
}
int main(){
	freopen("robot.in","r",stdin);
	freopen("robot.out","w",stdout);
	read();
	calc_all();
	calc_other();
	cout<<polf<<endl<<solf<<endl<<schf<<endl;
	return 0;
}