題目連結：
題目大意：
給定一正整數 Ｔ （１ ≦ Ｔ ≦ ５５５），代表接下來有 Ｔ 列輸入。每列輸入給定一正整數 Ｎ （１ ≦ Ｎ ≦ ５５, ５５５）。求是否存在一 Ｎ 位數長的正整數，其可以 ５ ^ Ｎ 整除且每一位皆為奇數。
如果存在多個這樣的數，請輸出最小的那一個；如果不存在，請輸出「-1」。
範例輸入：
2
2
3
範例輸出：
75
375
解題思維：
首先，我們要證明對於任意正整數 Ｎ ，皆可以找到唯一的、每一位皆是奇數且可被 ５ ^ Ｎ 整除的一個正整數：
假設我們已知 Ｎ ＝ ｋ 的答案，並假定為其值為 Ｐｋ × ５ ^ ｋ ，其中 Ｐｋ 為一正整數。
而當 Ｎ ＝ ｋ ＋ １ 時，Ｐｋ + １ × ５ ^ （ｋ ＋ １） ＝ ｑ × １０ ^ ｋ＋ Ｐｋ × ５ ^ ｋ ，其中 ｑ ＝ １ 、 ３ 、 ５ 、 ７ 、 ９ 其中一個數字。原因如下：
將上述等式簡化為： Ｐｋ + １ ＝ （ｑ × ２ ^ ｋ ＋ Ｐｋ） ÷ ５。所以我們要找到一個整數 ｑ 滿足 ｑ × ２ ^ ｋ ＋ Ｐｋ 取 ５ 的餘數為 ０ （≡ ０ ｍｏｄ ５）。
而 Ｐｋ 取 ５ 的餘數的可能值為 ０ ～ ４ 全部包含，但是 ２ ^ ｋ 的可能值只有 １ ～ ４ 。且我們已知 １ 、 ３ 、 ５ 、 ７ 、 ９ 取 ５ 的餘數分別為 １ 、 ３ 、 ０ 、 ２ 、 ４ ，也就是數字 ０ ～ ４ 都包含了。
因此，對於任意可能的 ２ ^ ｋ、Ｐｋ 之值，我們皆可以找到一個（且唯一一個）奇數 ｑ 符合上式。
以上，證明了 Ｐｋ + １ × ５ ^ （ｋ ＋ １） ＝ ｑ × １０ ^ ｋ＋ Ｐｋ × ５ ^ ｋ。且我們已知 Ｎ ＝ １ 時的答案即為 ５ 。因而可以推及到任意正整數 Ｎ 。
綜合以上論述，命題成立。
從以上的證明我們可以看到：不會有需要輸出「-1」或是從多組解之中找出最小解的情況發生（畢竟是唯一解）。且 Ｎ ＝ ｋ ＋ １ 的解之末 ｋ 位數即是 Ｎ ＝ ｋ 的解。
因此，我們可以利用大數運算，持續更新出 ２ ^ ｋ 、以及上面提及過的 Ｐｋ 之值，來求出新的 ｑ 值以及 Ｐｋ + １ 。
而把所有求過的 ｑ 值串成一個字串，即 Ｎ ＝ ５５, ５５５ 的答案，而末 ｋ 位數的數字即為 Ｎ ＝ ｋ 的解。
但是因為迴圈跑的過程需要計算 ２ ^ ｋ 、 Ｐｋ 且迴圈要從 ２ 跑到 ５５５５５ 。如果大數的運算之存取是把每一位分別放在 １ 格陣列之位置裡，則每一次計算都要跑過至少 Ｎ × log（２）位數，迴圈要跑 Ｎ 次。所以時間複雜度為 Ｏ（Ｎ ^ ２）加上不小的常數。
而如果是將一個數字以每 １８ 位數為一組（一起存在同一格陣列位置裡），則一次的計算量大約降至 ９３０ × ２ 次的運算。因此上面的時間複雜度之常數降低了不少。
因此可以在 １ 秒內把 Ｎ ＝ １ ～ ５５, ５５５ 的結果先算出來，再根據輸入的 Ｎ 值輸出相應的答案。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
