1965 . 大陸人系列1：傳說中的log
TopCoder
Description
有一天，大陸人閒來無事時翻著其他國家的人寫的論文。忽然，有一個演算法吸引了他的注意：這個演算法可以在$O(C)$預處理之後，$O(1)$查詢兩個小於等於C的數的最大公因數。
瞬間，十三億人都驚呆了。竟然有如此漂亮的方法！於是大陸人立刻仔細看了論文，並實作了這個演算法。結果，不實作還好，寫完一計時，居然比普通的$O(\log C)$演算法還慢！
為了，大陸人決定先從區間極值問題（RMQ）下手，試著讓$O(1)$還是比$O(\log N)$（zkw線段樹）快……
Input Format
本題沒有輸入，如果你輸入了任何東西可能會導致各種不可預期的結果(?)。
請#include "lib1965.h"之後實作下列函數，如果你的函數名稱不對或者長得不像下面那行，你將會獲得一個CE。
void init(int N, uint64_t C[]);：傳入一個長度為$N$的整數陣列$C_0, C_1, \cdots, C_{N-1}$。為了大陸人實作方便，保證C中的元素兩兩不相同。
uint64_t RMQ(int a, int b);：本函數必須回傳$C_a, C_{a+1}, \cdots, C_{b-1}$所有元素之中的最大值是多少。保證$0\leq a<b\leq N$。
對於所有的測資，$N\leq 10^ 7, Q\leq 3\times 10^ 7$，其中$Q$是呼叫RMQ的次數。
對於27%的測資，$N\leq 10^ 6, Q\leq 10^ 6$。
一次執行當中，init函數只會被呼叫一次。
注意：如果你在程式裡實作了main()函式，你也會獲得一個CE。
Output Format
本題沒有輸出，如果你輸出了任何東西，你將會獲得一個WA。
Hints
如果你想要獲得滿分的話，你可能要試著動態開記憶體。
Problem Source
Judge / Description by Yihda Yol
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 4 |
| 2 | 2~4 | 23 |
| 3 | 5~7 | 37 |
| 4 | 2~9 | 33 |
| 5 | 0~1 | 3 |