NOI 2002 机器人M号

该问题的数学模型是数论问题。机器人M号的所有老师就是小于M大于1M的所有约数,M号机器人的独立数就是小于M于M互质的数的个数,即为M的欧拉函数φ(M)。

把M分解为P1^e1P2^e2...*Pk^ek,欧拉函数有公式为

φ(M)=(P1-1)P1^(e1-1) (P2-1)P2^(e2-1) ... (Pk-1)Pk^(ek-1)

于是所有“政客”的独立数之和就是M的奇质因数中选出偶数个不同的质因数乘积的欧拉函数值之和,“军人”则是选出奇数个。“学者”无法直接 算出,然我们知道除了“政客”和“军人”就是学者,只需用小于M的M的所有约数的独立数之和减去“政客”和“军人”的独立数即可。可以证明,M的所有约数 的欧拉函数之和等于M。

求“政客”和“军人”分别的独立数之和,可以递推求出。定义F[i]为M的所有大于2的质因数中的选择i个质因数的欧拉函数和。F[j] = F[j] + F[j-1] * (P[i]-1) 。“政客”的独立数之和就是∑F[i] (i为偶数),“军人”的独立数之和就是∑F[i] (i为奇数)。

/* 
 * Problem: NOI2002 robot
 * Author: Guo Jiabao
 * Time: 2009.5.19 17:43
 * State: Solved
 * Memo: 欧拉函数
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXK=1001,MOD=10000;
using namespace std;
int P[MAXK],E[MAXK],F[MAXK],r1,r2,r3,M=1,K;
void init()
{
    freopen("robot.in","r",stdin);
    freopen("robot.out","w",stdout);
    scanf("%d",&K);
    for (int i=1;i<=K;i++)
        scanf("%d%d",&P[i],&E[i]);
}
int QuickPower(int a,int k)
{
    if (k==1)
        return a % MOD;
    int t = QuickPower(a,k/2);
    t = t * t % MOD;
    if (k%2)
        t = t * a % MOD;
    return t;
}
void solve()
{
    int i,j,a=1;
    if (P[1]==2)
        a=2;
    F[0]=1;
    for (i=a;i<=K;i++)
        for (j=i-a+1;j>=1;j--)
            F[j] = ( F[j] + F[j-1] * (P[i]-1) ) % MOD;
    for (i=1;i<=K-a+1;i++)
        if (i%2)
            r2 = (r2 + F[i]) % MOD;
        else
            r1 = (r1 + F[i]) % MOD;
    for (i=1;i<=K;i++)
        M = ( M * QuickPower(P[i],E[i]) ) % MOD;
    r3 = (M + MOD + MOD + MOD - r1 - r2 - 1) % MOD;
}
int main()
{
    init();
    solve();
    printf("%dn%dn%dn",r1,r2,r3);
    return 0;
}
<h2><span class="mw-headline">机器人M号 </span></h2>

【问题描述】

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&lt;=k&lt;=1000),k是m的不同的素因子个数。

以下k行,每行两个整数,pi, ei,表示m的第i个素因子和它的指数(i = 1, 2, …, k)。p1, p2, …, pk是不同的素数,m=p1^e1 * p2^e2 * ... * pk^ek。所有素因子按照从小到大排列,即p1&lt;p2&lt;…&lt;pk。输入文件中,2&lt;=pi&lt;10,000, 1&lt;=ei&lt;=1,000,000。
【输出文件】

输出文件包括三行。

第一行是机器人m号和它的老师中,所有政客的独立数之和除以10000的余数。

第二行是机器人m号和它的老师中,所有军人的独立数之和除以10000的余数。

第三行是机器人m号和它的老师中,所有学者的独立数之和除以10000的余数。
【样例输入】
<pre>3
2 1
3 2
5 1</pre>
【样例输出】
<pre>8
6
75</pre>
【样例说明】

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

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

相关日志