#20648: 解題方法
fdhs109_TG
(fdhs109_TG)
學校
:
桃園市私立復旦高級中學
編號 : 107649
來源 : [140.114.123.88]
最後登入時間 ：
2024-09-05 18:00:49
其實在數字很大的時候，做排列+判斷質數會很慢
可以先自己多測幾組測資
就會發現，數字大於一定值的時候，就要輸出 0
對於相關的知識可以 google "可交換質數"
#20649: Re:解題方法
asnewchien@gmail.com
(david)
學校
:
不指定學校
編號 : 68108
來源 : [122.117.95.179]
最後登入時間 ：
2024-11-04 20:21:51
這題我用 python 建表
建到 4 位數 17ms
建到 7 位數 0.2s
建到 8 位數 0.9s
#20650: Re:解題方法
asnewchien@gmail.com
(david)
學校
:
不指定學校
編號 : 68108
來源 : [122.117.95.179]
最後登入時間 ：
2024-11-04 20:21:51
建到 3 位數 17ms
#20651: Re:解題方法
fdhs109_GT
(GT coding)
學校
:
桃園市私立復旦高級中學
編號 : 102099
來源 : [140.114.123.88]
最後登入時間 ：
2024-09-05 18:00:19
建到 3 位數 17ms
其實 3 位後面就不用了 哈哈哈
因為題目有限制 n < 10000000
在範圍內最大就 3 位數，
下一個可交換質數 已大於題目範圍 是 1111111111111111111
所以 google 一下答案就出來囉～
#20730: Re:解題方法
雖然可以透過 google 找到可交換質數的數列，但我想這並非出題者的本意(?)
回到問題的原意是如何有效率地去檢驗 1e7 以內的可交換質數？
觀察『可交換質數』的定義可以發現：可交換質數除了２,５ 以外一定是由{１,３,７,９}的數字構成而且題目保證查詢的數字＜1e7
這句話的意思是我們需要處理的位數最多到６位。暴力法產生個數介於(1,6)的所有組合後檢驗該組合能產生所有排列的數字並逐一確認是否皆為質數。
這樣的做法需要的時間為 O(5^6) (每次可以從{×,１,３,７,９}挑個數字，×代表不選，最多挑滿６個)＋(最多)6個數字做排列後檢驗。
這種『非直覺』須透過觀察來實現的『暴力法』題目可以挑戰 c658小新的提款卡密碼。
#20731: Re:解題方法
asnewchien@gmail.com
(david)
學校
:
不指定學校
編號 : 68108
來源 : [122.117.95.179]
最後登入時間 ：
2024-11-04 20:21:51
看秒數就知道有沒有確實建表。
#20732: Re:解題方法
inversion
(「我們所認識的可符香是個像天使的好女孩」之葉林 *Cries...)
學校
:
國立清華大學
編號 : 43537
來源 : [49.159.6.107]
最後登入時間 ：
2022-05-28 19:29:12
我是在本地端暴力完後生成 < 10000000 裡的可交換質數。
因為數量不多，所以就直接建表了XD
ZeroJudge Forum