[ACM ] 386

作者deepking (wnuiayldh)

看板C_and_CPP

標題[ACM ] 386

時間Wed Jul 1 16:02:34 2009

http://uva.onlinejudge.org/external/3/386.html 方程式：a^3 = b^3 + c^3 + d^3 a<= 200 ,（a,b,c,d均大於1）語言：c 用暴力法寫四個迴圈去跑 code: http://nopaste.info/a97770cc90.html 時間：0.140 先把次方算完放在array 時間：0.100 請問有辦法讓他跑快一點嗎？要用什麼資料結構或演算法？可以給個方向嗎＠＠？ ------------------------------------------------- 如果要建表用bsearch 是用structure存 b,c,d ? for(j=2; j<200; j++){ for(k=j; k<200; k++){ for(l=k; l<200; l++){ } } } 這樣要1313410項？＝＝？ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 122.122.32.152

推 ledia:比如說 binary search 07/01 16:09

→ ledia:不用每次都真的去乘, 一開始先乘好放在 array 裡 07/01 16:10

推 ledia:還有一些數論的加速, 如果 (a,b,c,d)=1, 那麼 a 是偶數 07/01 16:12

→ ledia:b, c, d 只有一個會是偶數 07/01 16:12

→ ledia:a 是奇數, b,c,d 就只會有一個是奇數 07/01 16:13

→ ledia:是說 sample output 怎麼沒有 9^3 = 1^3 + 6^3 + 8^3 ? 07/01 16:15

→ ledia:是我弄錯意思了嗎? 囧 07/01 16:15

→ ledia:啊, a, b, c, d > 1, 沒注意到 ... 07/01 16:16

→ deepking:XD 我應該先把條件打出來 sorry= =||| 07/01 16:18

→ deepking:來試看看先寫在array的方法！！謝啦～ 07/01 16:23

→ deepking:在論壇有看到說用hash table會比較快！是說先乘好在用 07/01 16:25

→ deepking:hash table 搜尋嗎？？ 07/01 16:26

推 ledia:對, 算是 binary search 的進階吧 key 是 a^3, value 是 a 07/01 16:30

→ ledia:啊, 怕你誤會, 他們的意思是先算出 b^3+c^3+d^3 再看這個 07/01 16:30

→ ledia:值有沒有出現在立方數的 hash table (預先建好) 裡 07/01 16:31

推 netsphere:這題還想過一些DP加速的方式 07/01 17:24

→ netsphere:A^3=B^3+C^3+D^3 => (xA)^3=(xB)^3+(xC)^3+(xD)^3 07/01 17:25

→ netsphere:Table[A]=Table[2A]=...=Table[xA] 07/01 17:25

→ netsphere:但會讓順序難以決定變得挺麻煩的所以作罷~ 07/01 17:27

※ 編輯: deepking 來自: 122.122.32.152 (07/01 17:57)

→ netsphere:修正一下 Table[xA]=x*Table[A] 好久以前的記憶了 07/01 18:01

推 ledia:bsearch 那個存 1^3 ~ 200^3 只要存 200 項就好 07/01 18:31

→ ledia:要再快的話把 a^3 - b^3 建 hash , 用 c^3+d^3 查 07/01 18:33

推 FRAXIS:用兩個陣列存 a^3 - b^3, b^3 + d^3 07/01 18:43

→ FRAXIS:分別排序之後找相同的元素.. 07/01 18:43

→ deepking:瞭解...搞亂掉了XD 07/01 19:04