TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3804
  • 题目
  • P3804机器人 M 号
    限制 : 时间限制 : - MS   空间限制 : 65536 KB
    评测说明 : 1000ms
    问题描述

    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 的余 数。 

    样例输入


    2  1 
    3  2 
    5  1 

    样例输出

    8
    6
    75

    提示

    【样例说明】 
        90 53^2 = ××=m 。90 号机器人有 10 个老师,加上它自己共 11 个。其中政
    客只有 15 号;军人有 3 号和 5 号;学者有 8 个,它们的编号分别是: 2,6,9,10,18,30,45,90。 


    来源  noi 2002