作者查詢 / utomaya
作者 utomaya 在 PTT [ puzzle ] 看板的留言(推文), 共586則
限定看板：puzzle
看板排序：
1F推:OEIS有數列 http://oeis.org/A19200812/25 00:35
2F→:目前只有24人解出來 看樣子不是容易的題目吶?12/25 01:13
3F推:解掉了! 第37名，排列組合的問題!!!12/25 12:09
4F→:OEIS完全幫不上忙 僅供參考而已12/25 12:11
11F→:今天應該是Easy題，才那麼多人搶，搶到當機01/01 01:02
12F→:若沒猜錯的話 出題的難易度有固定pattern,HMEMEMHMEMEMH..01/01 01:05
13F→:猜錯了? 這次竟然是M(Medium)01/01 01:23
14F→:果然沒猜錯 真的是Easy題!01/01 01:29
3F推:如果要跑暴力破解法 應該不會那麼難12/17 19:49
4F→:不過要跑一分鐘以內 就有點難度12/17 19:49
5F→:OEIS中已經有說同樣的prime signature 其a(n)是一樣的12/17 19:51
6F→:所以不必每一個數都去算其a(n), 同樣的prime signature12/17 19:52
7F→:算一就好, 並存到表格內(應該是Hash)，遇到同樣的prime12/17 19:54
8F→:signature, 再從hash table取出即可12/17 19:54
9F→:素數的枚舉，也不用枚舉到10^10即可, 枚舉到10^8即可12/17 19:57
10F→:大如10^8的素數,假若為p, p*1~p*100其a(n)等於101~101*10012/17 19:58
11F→:所以只要算出小於(10^10)/1,(10^10)/2,...,(10^10)/10012/17 20:00
12F→:的素數個數即可12/17 20:00
13F→:我的方法, 如果是用C++加上現在主流的PC(core i7)12/17 20:03
14F→:應該是十分鐘以內可以跑出結果12/17 20:04
13F推:我也可以確定 A_一萬 的末九位是 84378398812/06 00:49
14F→:若沒算錯的話 A_1萬=671765339622246704507471884378398812/06 00:50
15F→:加油了! 還剩4個席位...12/06 00:51
22F推:如果沒算錯的話 A_{10^18}化作二進制應該有1126216794位數12/09 00:59
23F→:好大的數字12/09 01:00
1F→:老梗題了 歐拉的兩數平方和問題, 這次換成3個數的平方和11/28 00:58
2F→:r^2=x^2+y^2+z^3 ==> (r-x)(r+x)=y^2+z^211/28 01:04
3F→:枚舉x, 就變成歐拉的兩數平方和問題11/28 01:04
1F→:原來是這樣解的 77777777=7*11*73*101*13703/28 12:02
2F→:A(10^9)+B(10^9)分別除以這5個質數的餘數 都有一個循環03/28 12:04
3F→:循環的周期剛好是 p*(p-1)03/28 12:04
4F→:分別求出對某一個質數的餘數 再總和求出除77777777的餘數03/28 12:06
5F→:因為這題是牽涉到ordered bell number,只有O(n^2)的演算法03/28 12:07
6F→:剛好求餘的設計選了一個特別的數77777777 可以免去O(n^2)03/28 12:08
7F→:慢了一個小時 只拿到21 殘念!03/28 12:09
8F→:簡單來說 這題是個陷阱題 數字再大(10^18)還是可以在1分鐘03/28 12:31
9F→:內跑完...這種陷阱，倒是很符合謎題的特質03/28 12:32
1F推:我可以算出來n=1->100 C(n)=17575了03/13 12:49
2F→:不過 到20000要跑8個小時耶 怎麼要那麼久?03/13 12:50
3F→:寫錯 20000要5分鐘~~ 200000要八個小時03/13 12:52
5F推:應該是大家找不到1分鐘的解法吧03/13 12:57
6F→:應該是有1分鐘內的解法03/13 12:57
7F→:不過 我的電腦很慢 只有1.7GHz 換快一點的電腦應該可以03/13 12:58
8F→:3小時以內!03/13 12:58
9F→:如果跑耗時得程式的話 應該3小時以內就有第1個解答者才對?03/13 13:00
11F推:跑了6小時 結果答案是錯的 而題目所給的hint數字我都符合03/13 19:23
12F→:終於知道這題難在哪了? 難怪現在為止沒人做出來03/13 19:24
13F→:而且我確定不是溢位的問題 應該是演算法有錯03/13 19:25
14F→:正確答案應該有12位數 而且比我的答案略小(26359....)03/13 19:28
37F推:我也得出了sum n=1~1000 C(n) = 312034503/19 13:58
38F→:不過Euler拒絕了我的答案!03/19 13:59
39F推:現在收斂到了260568268429 不過似乎還不是最佳解03/19 14:03
40F→:這大概是Euler有史以來最難的題目 比第289題還要難!03/19 14:29
41F推:解掉了 令人崩潰的題目!!03/19 23:58
42F→:sum n=1~1000 C(n) = 3120345 是正確的03/19 23:59
43F→:跑了16秒 果然是有一分鐘內的解法 記憶體也不需要太多03/20 00:04
44F→:之前錯的答案 開頭4碼竟是正確的!! 差了那麼一點03/20 00:09
46F→:3秒鐘!! 不過論壇裡有人跑到0.25秒03/24 20:14
47F→:有人需要大一點的測資嗎? sum n=1~5000 C(n) = 10304728803/24 20:15
48F→:單看一個不準 要看總和才準...03/24 20:15
49F→:我之前錯的答案 C(5000)是對的 但C(4000)卻錯了03/24 20:16
50F推:0.046秒!!! 天啊~ 我比它還快了 現在是論壇裡最快的!03/31 00:43
51F→:可以跑到5億:C(5*10^8) 花了19分鐘又20秒03/31 00:44
52F→:但我的電腦很慢，如果用新型的電腦 應該可以6分鐘內03/31 00:45
4F推:歐氏對局 http://tinyurl.com/4m4zzdl 裡面有公式02/20 21:38
5F→:不過這公式複雜度是O(N) 要算到S(10^16) 還要一點輔助02/20 21:40
6F→:我確定沒有別的公式了 這就是ProjectEuler賊的地方02/20 21:41
7F→:光靠公式 還不足以解出；；不然的話 20席早滿了02/20 21:42
8F→:ProjectEuler那些玩家 搜尋公式可是很厲害的!02/20 21:43
9F→:有時候 解個半死 ；進到論壇，才發現別人早就找到公式了02/20 21:44
10F→:這公式是沒錯的, 我驗證過, S(10^4)一下就出來了02/20 21:46
11F→:如果你不想看那麼多 直接跳到定理7, 那裡有結論02/20 21:47
12F→:還有，解題的關鍵 不在這個公式(非常確定)，要靠自己!02/20 21:49
13F推:解題的關鍵 應該在費氏數列的特性 Fn=Fn-1+Fn-202/20 21:52
14F→:要用divide and conquer去做 很難寫! 所以第1天只有13人02/20 21:53
15F→:應該這樣說吧 利用這公式在計算時 你會發現很多計算是重複02/20 21:54
16F→:所以可以把計算的部份重複的部份 用divide and conquer02/20 21:56
17F→:去化簡!02/20 21:56
18F推:對了 為了怕誤導大家 我再把話說清楚一點02/21 00:30
19F→:解題的關鍵 不在這個公式, 不是說不要利用這個公式02/21 00:30
20F→:當然還要利用公式，只是不要嘗試再去化簡公式02/21 00:31
21F→:這公式已經是最簡了02/21 00:31
22F推:果然跟猜想的一樣 利用fibonacci數列的特性02/23 06:57
23F→:S(10^16)mod 7^10 不用一毫秒 答案就出來了 複雜度O(logN)02/23 06:59
4F推:用BFS得出M(n)=n*(n+2)01/23 12:06
5F→:不過要解這方程式n*(n+2)=k*(k+1)/2到第40項 還真有點難度01/23 12:08
2F推:多謝 很詳細01/03 22:49
3F推:回j大 其實不是這陣子 其實PE一直以來就是兩種類型交替01/03 22:53
4F→:一種是難的題型一種是快的題型 快的題型通常在1hr左右搶光01/03 22:55
5F→:我是指20席在1hr左右被搶光01/03 22:56
3F→:跟我最初的構想一樣 這個區域離爆炸中心點水平方向x公尺處01/02 21:47
4F→:垂直高度都是一樣的 所以可切成薄圓柱 總和其體積01/02 21:49
5F→:就跟微積分的做法一樣 只是我不知道如何列式? 只好硬幹了01/02 21:50