1865 . 小向的魔法術鬣
TopCoder
Tags
Description
還記得小向嗎？對，就是那個天龍國的天才魔法少女。
身為天龍國的魔法少女，研究一兩種魔法術鬣是一定要的，小向常常窩在魔法書堆裡面研究她抓到的魔法術鬣。
有天，小向發現了一種奇特的魔法術鬣，她決定要好好的跟她的新術鬣玩一下。
這時候問題就來了，
我們都知道，魔法術鬣是種脾氣很壞的魔法生物，他們常常會很亂又很長，但是要是不找出他們的規律，小向就會很煩躁導致一整週失眠。
還好小向已經發現一種簡化魔法術鬣的方法了。
魔法術鬣是由一長串的魔法整數構成的，而小向有兩種魔法可以幫助她簡化魔法術鬣，分別是：
- 檢查魔法術鬣第i項是否可以整除第i+1項。
- 把魔法術鬣第i項變成第i項和第i+1項的魔法最大公因數，把第i+1項變成第i項和第i+1項的魔法最小公倍數。
只要讓魔法術鬣的每一項(最後一項除外)全部都可以整除他的下一項，小向就可以輕鬆的研究魔法術鬣了。
小向為了要施魔法所以必須專心，於是她將操作和檢查的工作交給你，天龍國的魔法少女實習生，請你使用小向的魔法，簡化魔法術鬣。
Input Format
本題為互動題，程式開始前請先 #include "lib1865.h"
你可以使用四個函數，分別是：
int GetN();，取得魔法術鬣的長度N。bool Magic_Isdivide(i);，使用魔法檢查魔法術鬣的第i項是否可以整除第i+1項。void Magic_Operate(i);，使用魔法讓魔法術鬣第i項變成第i項和第i+1項的最大公因數，把第i+1項變成第i項和第i+1項的最小公倍數。void End();，當你覺得魔法術鬣已經簡化完畢後，請呼叫這個函數，小向會自動結束你的程式。
請不要輸入任何字元，也不要對魔法術鬣做不合理的操作，否則將會得到WA。
因為小向的魔力有限，你使用魔法的總次數不可以超過500000，否則小向也會給你一個WA。
對於10%的測資，$1 \leq N \leq 10$
對於100%的測資，$1 \leq N \leq 10^ 3$
Output Format
請不要輸出任何字元，否則會得到一個WA。
Hints
以下是一個不會CE，但是不一定會AC的範例程式。
#include "lib1865.h"
int main()
{
int n;
n = GetN();
for(int i = 0; i < n-1 ; i++)
{
if(!Magic_Isdivide(i)) Magic_Operate(i);
}
End();
return 0;
}
Problem Source
2015建中校隊入隊考試-複試
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~2 | 10 |
| 2 | 3~6 | 90 |