ETH官方钱包

切換
舊版
前往
大廳
主題

ZeroJudge - c643: 55555 解題心得

Not In My Back Yard | 2019-04-01 23:05:14 | 巴幣 0 | 人氣 412

題目連結:


題目大意:
給定一正整數 T (1 ≦ T ≦ 555),代表接下來有 T 列輸入。每列輸入給定一正整數 N (1 ≦ N ≦ 55, 555)。求是否存在一 N 位數長的正整數,其可以 5 ^ N 整除且每一位皆為奇數。

如果存在多個這樣的數,請輸出最小的那一個;如果不存在,請輸出「-1」。



範例輸入:
2
2
3


範例輸出:
75
375


解題思維:
首先,我們要證明對於任意正整數 N ,皆可以找到唯一的、每一位皆是奇數且可被 5 ^ N 整除的一個正整數

假設我們已知 N = k 的答案,並假定為其值為 P × 5 ^ k ,其中 P 為一正整數。

而當 N = k + 1 時,Pk + 1 × 5 ^ (k + 1) = q × 10 ^ k+ P × 5 ^ k ,其中 q = 1 、 3 、 5 、 7 、 9 其中一個數字。原因如下:

將上述等式簡化為: k + 1 = (q × 2 ^ k + P) ÷ 5。所以我們要找到一個整數 q 滿足 q × 2 ^ k + P 取 5 的餘數為 0 (≡ 0 mod 5)。

而 P 取 5 的餘數的可能值為 0 ~ 4 全部包含,但是 2 ^ k 的可能值只有 1 ~ 4 。且我們已知 1 、 3 、 5 、 7 、 9 取 5 的餘數分別為 1 、 3 、 0 、 2 、 4 ,也就是數字 0 ~ 4 都包含了。

因此,對於任意可能的 2 ^ k、P 之值,我們皆可以找到一個(且唯一一個)奇數 q 符合上式。

以上,證明了 Pk + 1 × 5 ^ (k + 1) = q × 10 ^ k+ P × 5 ^ k。且我們已知 N = 1 時的答案即為 5 。因而可以推及到任意正整數 N 。

綜合以上論述,命題成立。



從以上的證明我們可以看到:不會有需要輸出「-1」或是從多組解之中找出最小解的情況發生(畢竟是唯一解)。且 N = k + 1 的解之末 k 位數即是 N = k 的解。

因此,我們可以利用大數運算,持續更新出 2 ^ k 、以及上面提及過的 P 之值,來求出新的 q 值以及 Pk + 1

而把所有求過的 q 值串成一個字串,即 N = 55, 555 的答案,而末 k 位數的數字即為 N = k 的解。

但是因為迴圈跑的過程需要計算 2 ^ k 、 P 且迴圈要從 2 跑到 55555 。如果大數的運算之存取是把每一位分別放在 1 格陣列之位置裡,則每一次計算都要跑過至少 N × log(2)位數,迴圈要跑 N 次。所以時間複雜度為 O(N ^ 2)加上不小的常數。

而如果是將一個數字以每 18 位數為一組(一起存在同一格陣列位置裡),則一次的計算量大約降至 930 × 2 次的運算。因此上面的時間複雜度之常數降低了不少。

因此可以在 1 秒內把 N = 1 ~ 55, 555 的結果先算出來,再根據輸入的 N 值輸出相應的答案。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

胖胖貓
這題根本TLE吃到飽= =
一開始自己寫,發現的 new 一個新的物件會浪費爆多的時間在複製值
後來我又寫了__int128版本想說會縮短進位次數結果反而吃TLE...
2019-04-02 16:40:53
Not In My Back Yard
這題真的不好搞,本人是看了出題者的提示,才想到要壓運算的時間常數的。

不曉得 icube 大神們怎麼壓到 0.2s 的,好猛XD
2019-04-02 18:15:39

相關創作

更多創作