#48148: 兩種解法(0.2s)(0.4s)


rsj00008 (西加008)

學校 : 基隆市私立二信高級中學
編號 : 49436
來源 : [114.24.22.164]
最後登入時間 :
2025-10-08 12:16:07

解法一========= 公式法,再搜答案 AC 0.2s
   Σ(1~H) == Σ(H~N) ==> (H-1)*(H)÷2 = (H+1+N)*(N-H)÷2
   ==> N = ( -1 + sqrt(1+8*H*H) ) / 2 即 k=sqrt(8*H^2+1) 需為完全平方數,且為奇數 , 因1 1不算,所以 H由2開始直到找到10個為止

解法二========= 爬行法,陣列循環使用 AC 0.4s且用了153MB
  *** 但記憶體不足,最後一組 H=46611179 ,N= 65918161 ,相差近2*10^7 ,所以 tot[開2千萬] 循環使用  ***
   起始設H=1,N=2動態計算前綴和tot[N+1]  ,且使用tot時索引有mod(2*10^7)
   while(Σ(H~N)<Σ(1~H)) {N++且計算新的前綴和tot[n%Mod]}
   if 相等,則產生一組
   while(Σ(H~N)>Σ(1~H)) {H++}