發表新討論
#11133: 到N = 7000 unsigned long long 就不夠用了 怎解?


iven00000000 (羽音穎次方)

學校 : 國立臺灣科技大學
編號 : 48522
來源 : [61.219.144.211]
最後登入時間 ：
2017-10-20 15:22:23
b797. V流星火雨 | From: [36.230.99.213] | 發表日期 : 2016-07-06 23:02

如題

到N = 7000 unsigned long long 就不夠用了 怎解?

不知道AC的大神們是怎解的?

我用DP+遞迴，算過的答案用陣列存起來

過程內容接近列舉大致如下

1.找小於N的最大平方數(設為sq, 其平方根為r)

2.把N-sq丟到下一層，下一層限制最大能拆解的完全平方數為(r-1)^2

3.持續做2，直到N < sq

大智的邏輯是這樣，細節先略過

不知道有沒有什麼方法可以加速?

 

 
#11141: Re:到N = 7000 unsigned long long 就不夠用了 怎解?


silithus (希利蘇斯)

學校 : 澳門培道中學
編號 : 33314
來源 : [60.246.116.246]
最後登入時間 ：
2023-09-19 17:00:10
b797. V流星火雨 | From: [60.246.209.23] | 發表日期 : 2016-07-08 00:09

如題

到N = 7000 unsigned long long 就不夠用了 怎解?

不知道AC的大神們是怎解的?

我用DP+遞迴，算過的答案用陣列存起來

過程內容接近列舉大致如下

1.找小於N的最大平方數(設為sq, 其平方根為r)

2.把N-sq丟到下一層，下一層限制最大能拆解的完全平方數為(r-1)^2

3.持續做2，直到N < sq

大智的邏輯是這樣，細節先略過

不知道有沒有什麼方法可以加速?

 



我是用大數運算+DP，不知道有沒有更佳的解法

 
ZeroJudge Forum