【机器人M号】题解

题目

题目描述

3030年，Macsy正在火星部署一批机器人。 第1秒，他把机器人1号运到了火星，机器人1号可以制造其他的机器人。 第2秒，机器人1号造出了第一个机器人——机器人2号。 第3秒，机器人1号造出了另一个机器人——机器人3号。 之后每一秒，机器人1号都可以造出一个新的机器人。第m秒造出的机器人编号为m。我们可以称它为机器人m号，或者m号机器人。 机器人造出来后，马上开始工作。m号机器人，每m秒会休息一次。比如3号机器人，会在第6，9，12，……秒休息，而其它时间都在工作。 机器人休息时，它的记忆将会被移植到当时出生的机器人的脑中。比如6号机器人出生时，2，3号机器人正在休息，因此，6号机器人会收到第2，3号机器人的记忆副本。我们称第2，3号机器人是6号机器人的老师。 如果两个机器人没有师徒关系，且没有共同的老师，则称这两个机器人的知识是互相独立的。注意：1号机器人与其他所有机器人的知识独立（因为只有1号才会造机器人），它也不是任何机器人的老师。一个机器人的独立数，是指所有编号比它小且与它知识互相独立的机器人的个数。比如1号机器人的独立数为0，2号机器人的独立数为1（1号机器人与它知识互相独立），6号机器人的独立数为2（1，5号机器人与它知识互相独立，2，3号机器人都是它的老师，而4号机器人与它有共同的老师——2号机器人）。 新造出来的机器人有3种不同的职业。对于编号为m的机器人，如果能把m分解成偶数个不同奇素数的积，则它是政客，例如编号15；否则，如果m本身就是奇素数或者能把m分解成奇数个不同奇素数的积，则它是军人，例如编号 3, 编号165。其它编号的机器人都是学者，例如编号2, 编号6, 编号9。 第m秒诞生的机器人m号，想知道它和它的老师中，所有政客的独立数之和，所有军人的独立数之和，以及所有学者的独立数之和。可机器人m号忙于工作没时间计算，你能够帮助它吗？ 为了方便你的计算，Macsy已经帮你做了m的素因子分解。为了输出方便，只要求输出总和除以10000的余数。

输入

输入文件的第一行是一个正整数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。

输出

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

样例输入

3

2 1

3 2

5 1

样例输出

8

6

75

样例解释

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

---

分析

很容易看出M的独立数就是与M互质的数，欧拉函数φ(M)指与M互质的数的个数，

如果M为P1 ^e1*P2 e2 ... Pk ^{ek（Pi是质因数），欧拉函数公式为φ(M)=(P1-1)P1} (e1-1) (P2-1)P2^(e2-1) ... (Pk-1)Pk^(ek-1)

令f[i]指选i个奇质数的独立数之和，显然递推式就是：

f[j]=(f[j]+f[j-1]*(zs[i][1]-1))%10000//zs[i][1]为第i个质数（即p[i]），zs[i][2]为第i个质数的指数（即e[i]）

那么政客的独立数之和就是当i%2=0的f[i]的总和，军人的独立数之和就是当i%2=1的f[i]的总和。而学者的独立数之和就是小于M的M的所有的约数的独立数之和，减去政客和军人的独立数之和，再减去1（因为1号机器人与其他所有机器人的知识独立，它也不是任何机器人的老师。）。小于M的M的所有的约数的独立数之和显然为：$$\sum_{d|M}\phi(d)$$

实际上$$\sum_{d|M}\phi(d)=M$$（这里有证明http://blog.csdn.net/chen1352/article/details/50695930）。

#include <cmath>

#include <cstdio>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;

int zs[11000][3],n,m,tot,f[1100];

int mi(int x,int y)

{

	int t=1;

	while(y>0)

	{

		if(y&1)	t=t*x%10000;

		x=x*x%10000;

		y>>=1;

	}

	return t;

}

int main()

{

	scanf("%d",&n);

	int i,j,k,l;

	for(i=1;i<=n;i++)

	{

		scanf("%d%d",&zs[i][1],&zs[i][2]);

	}

	int ans1=0,ans2=0,ans=0;/*ans2是政客，ans1是军人，ans是学者*/

	int g;

	if(zs[1][1]==2)

		g=2;

		else g=1;

	f[0]=1;

	for(i=g;i<=n;i++)

		for(j=i-g+1;j>=1;j--)

			f[j]=(f[j]+f[j-1]*(zs[i][1]-1))%10000;

	for(i=n-g+1;i>=1;i--)

	{

		if(i%2)

			ans1=(f[i]+ans1)%10000;

			else ans2=(ans2+f[i])%10000;

	}

	ans=1;

	for(i=1;i<=n;i++)

		ans=(ans*mi(zs[i][1],zs[i][2]))%10000;

	ans=(ans+3000000-ans1-ans2-1)%10000;

	cout<<ans2<<endl<<ans1<<endl<<ans<<endl;

}