P5746 [NOI2002] 机器人M号题目描述3030 年Macsy 正在火星部署一批机器人。第111秒他把机器人111号运到了火星机器人111号可以制造其他的机器人。第222秒机器人111号造出了第一个机器人——机器人222号。第333秒机器人111号造出了另一个机器人——机器人333号。之后每一秒机器人111号都可以造出一个新的机器人。第mmm秒造出的机器人编号为mmm。我们可以称它为机器人mmm号或者mmm号机器人。机器人造出来后马上开始工作。mmm号机器人每mmm秒会休息一次。比如333号机器人会在第666999121212…\ldots…秒休息而其它时间都在工作。机器人休息时它的记忆将会被移植到当时出生的机器人的脑中。比如666号机器人出生时222333号机器人正在休息因此666号机器人会收到第222333号机器人的记忆副本。我们称第222333号机器人是666号机器人的老师。如果两个机器人没有师徒关系且没有共同的老师则称这两个机器人的知识是互相独立的。注意111号机器人与其他所有机器人的知识独立因为只有111号才会造机器人它也不是任何机器人的老师。一个机器人的独立数是指所有编号比它小且与它知识互相独立的机器人的个数。比如111号机器人的独立数为000222号机器人的独立数为111111号机器人与它知识互相独立666号机器人的独立数为222111555号机器人与它知识互相独立222333号机器人都是它的老师而444号机器人与它有共同的老师——222号机器人。新造出来的机器人有333种不同的职业。对于编号为mmm的机器人如果能把mmm分解成偶数个不同奇素数的积则它是政客例如编号151515否则如果mmm本身就是奇素数或者能把mmm分解成奇数个不同奇素数的积则它是军人例如编号333编号165165165。其它编号的机器人都是学者例如编号222, 编号666, 编号999。第mmm秒诞生的机器人mmm号想知道它和它的老师中所有政客的独立数之和所有军人的独立数之和以及所有学者的独立数之和。可机器人mmm号忙于工作没时间计算你能够帮助它吗为了方便你的计算Macsy 已经帮你做了mmm的素因子分解。为了输出方便只要求输出总和除以100001000010000的余数。输入格式输入的第一行是一个正整数kkkkkk是mmm的不同的素因子个数。以下kkk行每行两个整数pip_ipi,eie_iei,表示mmm的第iii个素因子和它的指数(i1,2,…,k)(i1,2,\ldots,k)(i1,2,…,k)。p1,p2,…,pkp_1,p_2,\ldots,p_kp1,p2,…,pk是不同的素数∏i1kpiei\prod_{i1}^kp_i^{e_i}∏i1kpiei。所有素因子按照从小到大排列即p1p2…pkp_1p_2\ldotsp_kp1p2…pk。输出格式输出包括三行。第一行是机器人mmm号和它的老师中所有政客的独立数之和除以100001000010000的余数。第二行是机器人mmm号和它的老师中所有军人的独立数之和除以100001000010000的余数。第三行是机器人mmm号和它的老师中所有学者的独立数之和除以100001000010000的余数。输入输出样例 #1输入 #13 2 1 3 2 5 1输出 #18 6 75说明/提示样例解释m2×32×590m 2\times 3^2\times 590m2×32×590。909090号机器人有101010个老师加上它自己共111111个。其中政客只有151515号军人有333号和555号学者有888个它们的编号分别是2,6,9,10,18,30,45,902,6,9,10,18,30,45,902,6,9,10,18,30,45,90。数据范围对于全部的数据1≤k≤10001\le k\le 10001≤k≤10002≤pi10,0002\le p_i10,0002≤pi10,0001≤ei≤1,000,0001\le e_i\le 1,000,0001≤ei≤1,000,000。评分规则你在一个测试点的得分与你正确解决的问题数xxx有关。请注意对每一行即使不会解决该问题也请在该行输出一个数字否则 checker 将无法正确评分。xxx得分310271400C实现#includecstdio#defineMOD10000intf[1005][2];intfpow(intx,inty){intans1;while(y){if(y1)ansans*x%MOD;xx*x%MOD;y1;}returnans;}intmain(){intk;scanf(%d,k);inttot1;f[0][0]1;for(inti1;ik;i){intp,e;scanf(%d%d,p,e);tottot*fpow(p,e)%MOD;for(intj0;j1;j)f[i][j](f[i-1][j^1]*(p2?0:p-1)f[i-1][j])%MOD;}f[k][0](f[k][0]-1MOD)%MOD;printf(%d\n,f[k][0]);printf(%d\n,f[k][1]);printf(%d\n,((tot-f[k][0]-f[k][1]-1)%MODMOD)%MOD);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容