創作內容

0 GP

ZeroJudge - e293: 花開花落,雨初臨 解題心得

作者:Not In My Back Yard│2019-07-18 23:30:06│贊助:0│人氣:30
題目連結:


題目大意:
給定一正整數 n (n ≦ 5, 000),代表接下來 n 列,每列有一正整數(位數長 ≦ 5, 000)。求給定的正整數有無 100 以內的質因數。有的話,由小到大輸出那些質因數;反之,如果不存在任何 100 以內的質因數,輸出「Terrible Silence...」。

時限:0.4 s 。



範例輸入:
3
1
3
15


範例輸出:
Terrible Silence...
3
3 5


解題思維:
根據餘數的性質(詳情看這篇文章),我們可以一位數一位數地慢慢地取餘數,看最後的餘數是否為 0 ,即可判斷此數是否為某數的倍數。

但是因為 < 100 的質數有 25 個,所以最多可能會超過 5000 × 5000 × 25 個運算。因此直接做會超過時限。(計算是內建大數運算的語言直接取模也會超時)

而我們可以先把所有質數乘起來成為一個數字,然後用這個數字作為模數去對給定的數字取模。取完模之後再用這個餘數用上面的演算法去各自判斷各自是否為這些質數的倍數。

因為(x mod 6) mod 2=x mod 2、(x mod 6) mod 3=x mod 3,其他情況也是類似。因此先對 100 以內的質數之乘積(2 × 3 × 5 × …… × 97)取模可以將數字縮短到 37 位數以內。

因此,此時再對此餘數取模即可推得本來的餘數而不需大量的運算。

因此,有內建大數運算的語言(像 Python 、 Java 等)會比較輕易實行上面的方法;而 C++ 等的語言,不是要自己寫大數運算,就是要把那個乘積拆成好幾個部分使得可以用 long long 型態裝下等等。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
引用網址:https://home.gamer.com.tw/TrackBack.php?sn=4464863
All rights reserved. 版權所有,保留一切權利

相關創作

同標籤作品搜尋:程式題目解題心得|數論

留言共 0 篇留言

我要留言提醒:您尚未登入,請先登入再留言

喜歡★inversion 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:ZeroJudge - ... 後一篇:ZeroJudge - ...

追蹤私訊

作品資料夾

a29210494大家
出遊日常繪畫更新至part2 ლ(・´ェ`・ლ)看更多我要大聲說10小時前


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】