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

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

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

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

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

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

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

就算能過應該也很慢

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

建表不會過啦!

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

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

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

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

 

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

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

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

就算能過應該也很慢

 

 

 

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

建表不會過啦!

 

 

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

您能夠找到計算H(n)的演算法其時間複雜度為O(n^1/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)。

您能夠找到計算H(n)的演算法其時間複雜度為O(n^1/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。