Description
3030年，Macsy正在火星部署一批機(jī)器人。 第1秒，他把機(jī)器人1號(hào)運(yùn)到了火星，機(jī)器人1號(hào)可以制造其他的機(jī)器人。 第2秒，機(jī)器人1號(hào)造出了第一個(gè)機(jī)器人——機(jī)器人2號(hào)。 第3秒，機(jī)器人1號(hào)造出了另一個(gè)機(jī)器人——機(jī)器人3號(hào)。 之后每一秒，機(jī)器人1號(hào)都可以造出一個(gè)新的機(jī)器人。第m秒造出的機(jī)器人編號(hào)為m。我們可以稱它為機(jī)器人m號(hào)，或者m號(hào)機(jī)器人。 機(jī)器人造出來后，馬上開始工作。m號(hào)機(jī)器人，每m秒會(huì)休息一次。比如3號(hào)機(jī)器人，會(huì)在第6，9，12，……秒休息，而其它時(shí)間都在工作。 機(jī)器人休息時(shí)，它的記憶將會(huì)被移植到當(dāng)時(shí)出生的機(jī)器人的腦中。比如6號(hào)機(jī)器人出生時(shí)，2，3號(hào)機(jī)器人正在休息，因此，6號(hào)機(jī)器人會(huì)收到第2，3號(hào)機(jī)器人的記憶副本。我們稱第2，3號(hào)機(jī)器人是6號(hào)機(jī)器人的老師。 如果兩個(gè)機(jī)器人沒有師徒關(guān)系，且沒有共同的老師，則稱這兩個(gè)機(jī)器人的知識(shí)是互相獨(dú)立的。注意：1號(hào)機(jī)器人與其他所有機(jī)器人的知識(shí)獨(dú)立（因?yàn)橹挥?號(hào)才會(huì)造機(jī)器人），它也不是任何機(jī)器人的老師。 一個(gè)機(jī)器人的獨(dú)立數(shù)，是指所有編號(hào)比它小且與它知識(shí)互相獨(dú)立的機(jī)器人的個(gè)數(shù)。比如1號(hào)機(jī)器人的獨(dú)立數(shù)為0，2號(hào)機(jī)器人的獨(dú)立數(shù)為1（1號(hào)機(jī)器人與它知識(shí)互相獨(dú)立），6號(hào)機(jī)器人的獨(dú)立數(shù)為2（1，5號(hào)機(jī)器人與它知識(shí)互相獨(dú)立，2，3號(hào)機(jī)器人都是它的老師，而4號(hào)機(jī)器人與它有共同的老師——2號(hào)機(jī)器人）。 新造出來的機(jī)器人有3種不同的職業(yè)。對(duì)于編號(hào)為m的機(jī)器人，如果能把m分解成偶數(shù)個(gè)不同奇素?cái)?shù)的積，則它是政客，例如編號(hào)15；否則，如果m本身就是奇素?cái)?shù)或者能把m分解成奇數(shù)個(gè)不同奇素?cái)?shù)的積，則它是軍人，例如編號(hào) 3, 編號(hào)165。其它編號(hào)的機(jī)器人都是學(xué)者，例如編號(hào)2, 編號(hào)6, 編號(hào)9。 第m秒誕生的機(jī)器人m號(hào)，想知道它和它的老師中，所有政客的獨(dú)立數(shù)之和，所有軍人的獨(dú)立數(shù)之和，以及所有學(xué)者的獨(dú)立數(shù)之和?？蓹C(jī)器人m號(hào)忙于工作沒時(shí)間計(jì)算，你能夠幫助它嗎？ 為了方便你的計(jì)算，Macsy已經(jīng)幫你做了m的素因子分解。為了輸出方便，只要求輸出總和除以10000的余數(shù)。

Input
輸入文件的第一行是一個(gè)正整數(shù)k(1<=k<=1000)，k是m的不同的素因子個(gè)數(shù)。 以下k行，每行兩個(gè)整數(shù)，pi, ei,表示m的第i個(gè)素因子和它的指數(shù)(i = 1, 2, …, k)。p1, p2, …, pk是不同的素?cái)?shù)。所有素因子按照從小到大排列，即p1 < p2<… < pk。輸入文件中，2<=pi<10,000, 1<=ei<=1,000,000。

Output
輸出文件包括三行。 第一行是機(jī)器人m號(hào)和它的老師中，所有政客的獨(dú)立數(shù)之和除以10000的余數(shù)。 第二行是機(jī)器人m號(hào)和它的老師中，所有軍人的獨(dú)立數(shù)之和除以10000的余數(shù)。 第三行是機(jī)器人m號(hào)和它的老師中，所有學(xué)者的獨(dú)立數(shù)之和除以10000的余數(shù)。

Sample Input
3
2 1
3 2
5 1

Sample Output
8
6
75

Data Constraint

Hint
樣例解釋： m=2*3^2*5=90。90號(hào)機(jī)器人有10個(gè)老師，加上它自己共11個(gè)。其中政客只有15號(hào)；軍人有3號(hào)和5號(hào)；學(xué)者有8個(gè)，它們的編號(hào)分別是：2,6,9,10,18,30,45,90。
.
.
.
.
.
.

分析

歐拉函數(shù)+快速冪

梳理一下題目意思：
①獨(dú)立數(shù)是小于等于的m與互質(zhì)的數(shù)（包括1）
②一個(gè)數(shù)的老師是這個(gè)數(shù)的因數(shù)（不包括1）
③政客：對(duì)于一個(gè)數(shù)x，如果x可以轉(zhuǎn)換為偶數(shù)個(gè)不同的素因子的積，那它就是政客
④軍人：對(duì)于一個(gè)數(shù)x，如果x可以轉(zhuǎn)換為奇數(shù)個(gè)不同的素因子的積，那它就是軍人
⑤學(xué)者：對(duì)于m的老師x，如果x既不是政客又不是軍人，那它就是學(xué)者

---

一個(gè)數(shù)的獨(dú)立數(shù)其實(shí)就是它的歐拉函數(shù)和
設(shè)f[i]為m的所有大于2的質(zhì)因數(shù)中，選擇i個(gè)質(zhì)因數(shù)的歐拉函數(shù)和
那么政客的獨(dú)立數(shù)就是∑f[i]且(i%2==0)
軍人的獨(dú)立數(shù)就是∑f[i]且(i%2==1)

---

那么考慮學(xué)者的獨(dú)立數(shù)和怎么求？
這又要用到歐拉函數(shù)的一個(gè)性質(zhì)：n=∑d|n?(d)
m的所有的約數(shù)的歐拉函數(shù)之和為m
也就是說學(xué)者的獨(dú)立數(shù)和：m-軍人-政客-1
.
.
.
.
.

程序：

#include<iostream> using namespace std; int k,c[1001][2],f[1001],ans2=0,ans3=0,ans1=1,g,mod=10000; int work(int x,int y) {int ans1=1;while (y){if (y%2) ans1=(ans1*x)%mod;y/=2;x=(x*x)%mod;}return ans1; } int main() {cin>>k;for (int i=1;i<=k;i++) cin>>c[i][0]>>c[i][1];if (c[1][0]==2) g=2; else g=1;f[0]=1;for (int i=g;i<=k;i++)for (int j=i-g+1;j>=1;j--)f[j]=(f[j]+f[j-1]*(c[i][0]-1))%mod;for (int i=1;i<=k-g+1;i++)if (i%2) ans2=(ans2+f[i])%mod; else ans3=(ans3+f[i])%mod;for (int i=1;i<=k;i++) ans1=(ans1*work(c[i][0],c[i][1]))%mod;ans1=(ans1+10000000-ans2-ans3-1)%mod;cout<<ans3<<endl;cout<<ans2<<endl;cout<<ans1<<endl;return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/9499933.html

總結(jié)

以上是生活随笔為你收集整理的机器人M号的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。