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分;

相關日誌