a093: NOI2002 Day2.3.机器人M号
標籤 :
通過比率 : 90% (9 人 / 10 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2014-11-01 02:30

內容

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

輸入說明
输入文件 robot.in 的第一行是一个正整数k(1<=k<=1000),k 是m 的不同的
素因子个数。
以下k行,每行两个整数,pi, ei,表示m的第i个素因子和它的指数(i = 1, 2, …,
k)。p1, p2, …, pk是不同的素数,m = p1^e1 * p2^e2 * … * pk^ek ,所有素因子按照从小到大排列,即
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
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 2.0s , <1K
公開 測資點#1 (10%): 2.0s , <1K
公開 測資點#2 (10%): 2.0s , <1K
公開 測資點#3 (10%): 2.0s , <1K
公開 測資點#4 (10%): 2.0s , <1K
公開 測資點#5 (10%): 2.0s , <1K
公開 測資點#6 (10%): 2.0s , <1M
公開 測資點#7 (10%): 2.0s , <1M
公開 測資點#8 (10%): 2.0s , <1M
公開 測資點#9 (10%): 2.0s , <1M
提示 :

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

【评分标准】
输出文件包含三个数。如果你的程序算对了三个数,该测试点得10 分;如
果你的程序算对了两个数,该测试点得7分;如果你的程序算对了一个数,该测
试点得4分;如果你的程序一个数也没算对,该测试点得0分;

//这里我们取消部分分。

標籤:
出處:
NOI2002Day2第三题 [編輯:
liouzhou_101 (王启圣)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」