#15238: 解題方向/廢文


314159265358979323846264338327 ... (少年π)

School : 臺北市私立延平高級中學
ID : 69058
IP address : [223.136.179.30]
Last Login :
2024-04-29 19:11:35
d193. 11526 - H(n) -- UVa11526 | From: [223.136.74.230] | Post Date : 2018-09-22 14:04

我是少年π,這題是我的第300題了,所以來發一篇廢文

某人一直說我沒辦法300題的(我絕對不說是dartgoblin)tongue-out

但是我在電腦前戰鬥了15小時後,就順利把題數從275拉到300題了!coolsmile

感謝陪我做題目的朋友!(chad8787,oneal等延平程式設計班的好兄弟們!)

 

這題絕對不能用他給的函數直接貼上去(1000*4294967295=TLE吃到死)

想想看有沒有能讓迴圈只跑sqrt(n)次的辦法(8ms,344KB)

我沒有試過建表能不能過(4294967295次?)

就算能過應該也很慢

 

 

 

 
#15339: Re:解題方向/廢文


314159265358979323846264338327 ... (少年π)

School : 臺北市私立延平高級中學
ID : 69058
IP address : [223.136.179.30]
Last Login :
2024-04-29 19:11:35
d193. 11526 - H(n) -- UVa11526 | From: [114.136.170.140] | Post Date : 2018-09-29 12:41

我是少年π,這題是我的第300題了,所以來發一篇廢文

某人一直說我沒辦法300題的(我絕對不說是dartgoblin)tongue-out

但是我在電腦前戰鬥了15小時後,就順利把題數從275拉到300題了!coolsmile

感謝陪我做題目的朋友!(chad8787,oneal等延平程式設計班的好兄弟們!)

 

這題絕對不能用他給的函數直接貼上去(1000*4294967295=TLE吃到死)

想想看有沒有能讓迴圈只跑sqrt(n)次的辦法(8ms,344KB)

我沒有試過建表能不能過(4294967295次?)

就算能過應該也很慢

 

 

 

sorry!上文的所有4294967295要改成2147483647才對

建表不會過啦!

 

 

 
#21669: Re:解題方向/廢文


d2513850 (林勇智)

School : 崑山科技大學
ID : 5102
IP address : [114.140.72.110]
Last Login :
2024-10-20 17:35:39
d193. 11526 - H(n) -- UVa11526 | From: [163.26.71.40] | Post Date : 2020-07-04 19:09

我是少年π,這題是我的第300題了,所以來發一篇廢文

某人一直說我沒辦法300題的(我絕對不說是dartgoblin)

但是我在電腦前戰鬥了15小時後,就順利把題數從275拉到300題了!

感謝陪我做題目的朋友!(chad8787,oneal等延平程式設計班的好兄弟們!)

 

這題絕對不能用他給的函數直接貼上去(1000*4294967295=TLE吃到死)

想想看有沒有能讓迴圈只跑sqrt(n)次的辦法(8ms,344KB)

我沒有試過建表能不能過(4294967295次?)

就算能過應該也很慢

 

 

 

sorry!上文的所有4294967295要改成2147483647才對

建表不會過啦!

 

 


您能夠找到計算H(n)的演算法其時間複雜度為O(n1/2)嗎?

 
#21675: Re:解題方向/廢文


kkmomo (kkmomo)

School : No School
ID : 29247
IP address : [223.137.94.20]
Last Login :
2024-06-28 12:05:12
d193. 11526 - H(n) -- UVa11526 | From: [118.165.227.232] | Post Date : 2020-07-05 04:14


您能夠找到計算H(n)的演算法其時間複雜度為O(n1/2)嗎?


你可以把 -20<=n<=20 的所有 n / i , 1<= i <= n 印出來看看,就會很容易發現迴圈到最多只要到 sqrt(n) 次就可以,

 

順便一提,其實這題 UVa 本身題目敘述有缺陷,

在 C++ 中 signed int 最大值是 2147483647,

當 n = 2147483647 時,題目中的 H(n) 其實會因為 i 溢位而進入無窮迴圈,永遠得不到答案,

但用 UVa 的 uDebug 卻會得到答案是 46475828386,因為透過演算法 i 最多只跑到 sqrt(2147483647)。

 

 
#21676: Re:解題方向/廢文


kkmomo (kkmomo)

School : No School
ID : 29247
IP address : [223.137.94.20]
Last Login :
2024-06-28 12:05:12
d193. 11526 - H(n) -- UVa11526 | From: [114.24.233.119] | Post Date : 2020-07-05 13:37


您能夠找到計算H(n)的演算法其時間複雜度為O(n1/2)嗎?


你可以把 -20<=n<=20 的所有 n / i , 1<= i <= n 印出來看看,就會很容易發現迴圈到最多只要到 sqrt(n) 次就可以,

 

順便一提,其實這題 UVa 本身題目敘述有缺陷,

在 C++ 中 signed int 最大值是 2147483647,

當 n = 2147483647 時,題目中的 H(n) 其實會因為 i 溢位而進入無窮迴圈,永遠得不到答案,

但用 UVa 的 uDebug 卻會得到答案是 46475828386,因為透過演算法 i 最多只跑到 sqrt(2147483647)。

 

補充說一下,用 C++ 實際去執行原題的H(2147483647) 會發現程式會掛掉 Floating point exception (core dumped)

在 i = 2147483647 時 i=i+1 會溢位使得 i 變成從 -2147483648 開始遞增至 2147483647,不斷循環,

使得 i<=n 永遠成立 所以迴圈永遠不會結束,

但 i 重新遞增到 0 時, n/i 會導致 Floating point exception,使得程式 crash。

 
ZeroJudge Forum