宜昌需要做网站建设的公司,如何保持网站中的图片,企业级网站开发项目教程,自学网站建设好学吗正题 大意
因为题目比较gou#xff0c;所以就直接放题目了 机器人1号可以制造其他的机器人。 第2秒#xff0c;机器人1号造出了第一个机器人——机器人2号。 第3秒#xff0c;机器人1号造出了另一个机器人——机器人3号。 之后每一秒#xff0c;机器人1号都可以造出一个新…正题 大意
因为题目比较gou所以就直接放题目了 机器人1号可以制造其他的机器人。 第2秒机器人1号造出了第一个机器人——机器人2号。 第3秒机器人1号造出了另一个机器人——机器人3号。 之后每一秒机器人1号都可以造出一个新的机器人。第m秒造出的机器人编号为m。我们可以称它为机器人m号或者m号机器人。 机器人造出来后马上开始工作。m号机器人每m秒会休息一次。比如3号机器人会在第6912……秒休息而其它时间都在工作。 机器人休息时它的记忆将会被移植到当时出生的机器人的脑中。比如6号机器人出生时23号机器人正在休息因此6号机器人会收到第23号机器人的记忆副本。我们称第23号机器人是6号机器人的老师。 如果两个机器人没有师徒关系且没有共同的老师则称这两个机器人的知识是互相独立的。注意1号机器人与其他所有机器人的知识独立因为只有1号才会造机器人它也不是任何机器人的老师。 一个机器人的独立数是指所有编号比它小且与它知识互相独立的机器人的个数。比如1号机器人的独立数为02号机器人的独立数为11号机器人与它知识互相独立6号机器人的独立数为215号机器人与它知识互相独立23号机器人都是它的老师而4号机器人与它有共同的老师——2号机器人。 新造出来的机器人有3种不同的职业。对于编号为m的机器人如果能把m分解成偶数个不同奇素数的积则它是政客例如编号15否则如果m本身就是奇素数或者能把m分解成奇数个不同奇素数的积则它是军人例如编号 3, 编号165。其它编号的机器人都是学者例如编号2, 编号6, 编号9。 第m秒诞生的机器人m号想知道它和它的老师中所有政客的独立数之和所有军人的独立数之和以及所有学者的独立数之和。可机器人m号忙于工作没时间计算你能够帮助它吗 为了方便你的计算Macsy已经帮你做了m的素因子分解。为了输出方便只要求输出总和除以10000的余数。 解题思路
首先一个机器人m的独立数是φ(m)\varphi(m)φ(m)而老师的数量就是他的因数数量-2然后把M分解为 p1e1×p2e2×p3e3...×pkekp1^{e1}\times p2^{e2}\times p3^{e3}...\times pk^{ek}p1e1×p2e2×p3e3...×pkek 然后 φ(m)p1e1×p2e2...×pkek×(1−1p1)×(1−1p2)...×(1−1pk)\varphi(m)p1^{e1}\times p2^{e2}...\times pk^{ek}\times (1-\frac{1}{p1})\times (1-\frac{1}{p2})...\times (1-\frac{1}{pk})φ(m)p1e1×p2e2...×pkek×(1−p11)×(1−p21)...×(1−pk1) 之后 φ(m)(p1−1)p1e1−1×(p2−1)p2e2−1...×(pk−1)pkek−1\varphi(m)(p1-1)p1^{e1-1}\times (p2-1)p2^{e2-1}...\times (pk-1)pk^{ek-1}φ(m)(p1−1)p1e1−1×(p2−1)p2e2−1...×(pk−1)pkek−1 然后我们就可以发现政客的独立数就是在M的奇质因数中选择偶数个不同的乘起来的欧拉函数军人就是选奇数个。然后学者就是所以的独立数减去政客和军人。 选数我们可以用dp f[imod2][0]f[i\ mod\ 2][0]f[i mod 2][0]表示在M因子中只包含前i个的政客的欧拉函数 f[imod2][1]f[i\ mod\ 2][1]f[i mod 2][1]表示在M因子中只包含前i个的政客的欧拉函数 然后进行动态转移 f[imod2][0]f[(i1)mod2][0]f[(i1)mod2][1]∗(p−1)f[i\ mod\ 2][0]f[(i1)\ mod\ 2][0]f[(i1)\ mod\ 2][1]*(p-1)f[i mod 2][0]f[(i1) mod 2][0]f[(i1) mod 2][1]∗(p−1) f[imod2][1]f[(i1)mod2][1]f[(i1)mod2][0]∗(p−1)f[i\ mod\ 2][1]f[(i1)\ mod\ 2][1]f[(i1)\ mod\ 2][0]*(p-1)f[i mod 2][1]f[(i1) mod 2][1]f[(i1) mod 2][0]∗(p−1) 最后计算φ(m)\varphi(m)φ(m)减去最后的政客独立数总和和军人独立数总和 代码
#includecstdio
#define mods 10000
using namespace std;
int n,p,e,f[2][2],m1;
int ksm(int x,int k)//快速幂
{int ans1;while (k){if (k1) ans(ans*x)%mods;xx*x%mods;k/2;}return ans;
}
int main()
{scanf(%d,n);scanf(%d%d,p,e);mm*ksm(p,e)%mods;if (p2) f[1][0]1;else{f[0][0]1;f[1][0](f[0][0]f[0][1]*(p-1)%mods)%mods;f[1][1](f[0][1]f[0][0]*(p-1)%mods)%mods;}//初始化sro xjqのdalao orzfor (int i2;in;i){scanf(%d%d,p,e);mm*ksm(p,e)%mods;f[i1][0](f[~-i1][0]f[~-i1][1]*(p-1)%mods)%mods;f[i1][1](f[~-i1][1]f[~-i1][0]*(p-1)%mods)%mods;//动态转移}f[n1][0]--;m((m-1-f[n1][0]-f[n1][1])%modsmods)%mods;//计算学者printf(%d\n%d\n%d,f[n1][0],f[n1][1],m);
}
