NOI 2002 機器人M號
本文正體字版由OpenCC轉換
該問題的數學模型是數論問題。機器人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<=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的餘數。
【樣例輸入】
<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分；
上次修改時間 2017-02-03