TopCoder

User's AC Ratio

89.7% (35/39)

Submission's AC Ratio

29.6% (75/253)

Description

還記得小向嗎?對,就是那個天龍國的天才魔法少女。
身為天龍國的魔法少女,研究一兩種魔法術鬣是一定要的,小向常常窩在魔法書堆裡面研究她抓到的魔法術鬣。
有天,小向發現了一種奇特的魔法術鬣,她決定要好好的跟她的新術鬣玩一下。

這時候問題就來了,
我們都知道,魔法術鬣是種脾氣很壞的魔法生物,他們常常會很亂又很長,但是要是不找出他們的規律,小向就會很煩躁導致一整週失眠。
還好小向已經發現一種簡化魔法術鬣的方法了。
魔法術鬣是由一長串的魔法整數構成的,而小向有兩種魔法可以幫助她簡化魔法術鬣,分別是:

  1. 檢查魔法術鬣第i項是否可以整除第i+1項。
  2. 把魔法術鬣第i項變成第i項和第i+1項的魔法最大公因數,把第i+1項變成第i項和第i+1項的魔法最小公倍數。

只要讓魔法術鬣的每一項(最後一項除外)全部都可以整除他的下一項,小向就可以輕鬆的研究魔法術鬣了。

小向為了要施魔法所以必須專心,於是她將操作和檢查的工作交給你,天龍國的魔法少女實習生,請你使用小向的魔法,簡化魔法術鬣。

Input Format

本題為互動題,程式開始前請先 #include "lib1865.h"
你可以使用四個函數,分別是:

  1. int GetN(); ,取得魔法術鬣的長度N。
  2. bool Magic_Isdivide(i);,使用魔法檢查魔法術鬣的第i項是否可以整除第i+1項。
  3. void Magic_Operate(i);,使用魔法讓魔法術鬣第i項變成第i項和第i+1項的最大公因數,把第i+1項變成第i項和第i+1項的最小公倍數。
  4. void End();,當你覺得魔法術鬣已經簡化完畢後,請呼叫這個函數,小向會自動結束你的程式。

請不要輸入任何字元,也不要對魔法術鬣做不合理的操作,否則將會得到WA。
因為小向的魔力有限,你使用魔法的總次數不可以超過500000,否則小向也會給你一個WA。

對於10%的測資,$1 \leq N \leq 10$
對於100%的測資,$1 \leq N \leq 10^ 3$

Output Format

請不要輸出任何字元,否則會得到一個WA。

Sample Input

本題沒有輸入。

Sample Output

本題沒有輸出。

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

For Testdata: 0 ~ 2, Score: 10
For Testdata: 3 ~ 6, Score: 90
No. Time Limit (ms) Memory Limit (KiB)
0 1000 65536
1 1000 65536
2 1000 65536
3 1000 65536
4 1000 65536
5 1000 65536
6 1000 65536