Re: [問題] 摳醬的第三題
看板Prob_Solve (計算數學 Problem Solving)作者Leon (Achilles)時間11年前 (2013/04/15 07:13)推噓5(5推 0噓 9→)留言14則, 3人參與討論串3/4 (看更多)
※ 引述《RockLee (Now of all times)》之銘言:
: ※ 引述《vocaloid (void *)》之銘言:
: : https://code.google.com/codejam
: : 參考答案好像還沒公佈
: : 請問第三題怎麼作比較有效率呢?
: : large input 1 - 10 ^ 14
: : 2 - 10 ^ 100
: : 第一個我是跑測資前先建表 http://ideone.com/DDA2Sn
: : 第二個本來想offline建但不知會跑多久... 10^30就花了3分鐘
: 假設我們定義 fair_root 為本身是回文且它的平方也是回文
: 我是先建到 15 位數的表觀察它的規律性
: 發現從 N = 4 位數開始
: 有可能的 candidates 只有 N - 2 位數的 fair_root 在頭尾第二位補 0 或 1
: 例如 N = 6 的 fair_root 為:
: 100001
: 101101
: 110011
: 111111
: 200002
: 則 N = 8 的 fair_root 的 candidates 為:
: 1 0 0000 0 1
: 1 0 0110 0 1
: 1 0 1001 0 1
: 1 0 1111 0 1
: 2 0 0000 0 2
: 1 1 0000 1 1
: 1 1 0110 1 1
: 1 1 1001 1 1
: 1 1 1111 1 1
: 2 1 0000 1 2
: 對這十個 candidates 實際驗算可發現 N = 8 的 fair_root 共九個:
: 10000001
: 10011001
: 10100101
: 10111101
: 11000011
: 11011011
: 11100111
: 11111111
: 20000002
: 用這規律性去建表即使 online 建到 N = 50 的表也夠快
嗯.. 你確定嗎?
用 0,1,2 去造的好處是可以處理 進位 的狀況
但, 考慮一下這個數字
522808225
這個是用 5 當個位數造出來的.
請問你的規律性找的到這個數字嗎?
實際上, 就我所知, 這仍然是個 open problem.
這裡有解釋 necessay condition, 但是沒有給出 sufficient.
http://arxiv.org/pdf/1210.7593v1.pdf
這個作者頗有名氣, 不過這篇還沒有 review 過
所以讀的時候自己要注意.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 142.136.125.30
推
04/15 07:40, , 1F
04/15 07:40, 1F
→
04/15 07:41, , 2F
04/15 07:41, 2F
→
04/15 07:53, , 3F
04/15 07:53, 3F
→
04/15 07:53, , 4F
04/15 07:53, 4F
推
04/15 08:05, , 5F
04/15 08:05, 5F
→
04/15 08:10, , 6F
04/15 08:10, 6F
推
04/15 08:24, , 7F
04/15 08:24, 7F
→
04/15 08:24, , 8F
04/15 08:24, 8F
推
04/15 10:37, , 9F
04/15 10:37, 9F
推
04/15 12:09, , 10F
04/15 12:09, 10F
→
04/15 12:09, , 11F
04/15 12:09, 11F
→
04/15 12:10, , 12F
04/15 12:10, 12F
→
04/15 12:10, , 13F
04/15 12:10, 13F
→
04/15 12:11, , 14F
04/15 12:11, 14F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章