#20495: 解法大全


lawrence910426@gmail.com (l4wr3nc3)

School : 新北市立板橋高級中學
ID : 67988
IP address : [140.114.6.181]
Last Login :
2020-11-09 14:57:43
a007. 判斷質數 | From: [59.115.246.65] | Post Date : 2020-01-31 00:29

本題十分的簡單,絕對不像坊間所說的「a007 根本毒瘤質數判斷題」,相信各位在閱讀完本篇題解後必定能夠解開這題的。

小弟有七個方法可以解開這題,以下將詳細的一一介紹。

---------------------------------------------------------------------------------------

一、米勒 - 拉賓算法 (Miller-Rabin Primilarity Test)

先備知識:

(一)、費馬小定理

(二)、快速冪

 

詳細介紹去網路上 Google

https://zh.wikipedia.org/wiki/%E7%B1%B3%E5%8B%92-%E6%8B%89%E5%AE%BE%E6%A3%80%E9%AA%8C

---------------------------------------------------------------------------------------

二、線性篩法建表 (Linear Sieve)

先備知識:線性篩法

引理一:對於任意整數 N,若是從 [1,sqrt(N)] 的所有質數皆不整除 N,則 N 必為質數

 

作法:

(一)、建立 [1,1e5] 的質數表

(二)、根據引理一,輸入 N 之後拿 [1,sqrt(N)] 的質數試除

---------------------------------------------------------------------------------------

三、對測資二分搜 (Binary Search)

先備知識:二分搜尋法

 

如果輸入的數字 N 大於我們所預期的,那就讓程式 Runtime Error;如果輸入的數字 N 小於我們所預期的,那就讓程式 Time Limit Exceed。

根據上述的作法,便能一一抓出測試資料了,令人訝異的,我們只需要進行 31 次上述的操作,就一定能找到一行測試資料!

若是你會撰寫網路爬蟲,可以使用爬蟲慢慢把測試資料爬出來;如果你不會的話也沒關係,慢慢手動找,也能找出所有資料的。

 

額外知識:整體二分搜

如果你會整體二分,你可以對整組測試資料整體二分,有助於提升找測資的效能。

---------------------------------------------------------------------------------------

四、打表建表 (Sieve of Eratosthenes)

先備知識:Sieve of Eratosthenes

 

同方法二,打表建表的時,只要跳過 (2,3,5) 這三個質數,通常執行效率就夠快了。

---------------------------------------------------------------------------------------

五、編譯器建表 (Compiler Sieve)

先備知識:constexpr syntax

 

同方法二,只不過這次是用編譯器來建立質數表,藉此獲得更短的執行時間,不過相對的,伺服器會需要相當久(甚至比執行時間還久)的編譯時間。

---------------------------------------------------------------------------------------

六、本機建表 (Local Sieve)

先備知識:使用程式生成程式碼、壓縮程式碼、宣告極大陣列


同方法二,只不過這次是在本機先建立質數表,再把質數表寫入你的 Submission。

這樣的好處是不需要浪費時間在執行上,也不需要浪費時間在編譯上,十分的優秀。

---------------------------------------------------------------------------------------

七、究極解法 (Ultimate Solution)

先備知識:一個熱忱的心

 

我們都知道,輸入的數字 N 是有範圍的。

只要在本機計算出每一種輸入的回答,再將每個回答寫入程式碼,便能做到 O(1) 回答題目了!

這樣不只能夠 AC 這題,還能夠成為 Ranklist 上第一名!!!

---------------------------------------------------------------------------------------

很顯然這題目一點都不毒瘤,現在大家都會了嗎?

大家加油,努力一下就能把這題寫掉了,祝大家都能過這一題 ><

 

 
ZeroJudge Forum