Mihai和Slavic正看著一群數量為$n$的青蛙，他們有各自的編號$1$ ~ $n$，一開始皆位於座標點0上，第$i$個青蛙有跳躍的長度$a_i$
每一秒鐘，第$i$個青蛙向前跳躍$a_i$個單位長。在青蛙向前跳之前，Mihai和Slavic可以在一個坐標中放置一個陷阱，以便捕獲所有穿過該坐標的青蛙。
然而，Mihai和Slavic不能離家太遠，所以他們最遠只能在離家單位$n$的地方放置陷阱(也就是在坐標為$1$ ~ $n$之間的點）以及他們不能放在座標為0的地方上，因為Mihai和Slavic很害怕青蛙。
你可以幫助Mihai和Slavic找到他們最多可以捕到多少青蛙嗎?
第一行輸入一個變數$t$，代表有$t$筆測資
每筆測資的第一行有一變數$n$，為青蛙的數量，同時為能放置陷阱的最遠地方。
第二行輸入$n$個數$a_i$，代表每隻青蛙跳躍的長度
輸出Mihai和Slavic最多能捕獲多少隻青蛙
每筆測資輸出結束後換行
3 5 1 2 3 4 5 3 2 2 2 6 3 1 3 4 9 10
3 3 3
不能在青蛙跳躍的途中捕獲，只能在青蛙跳躍結束時捕獲
$For$ $20$% $subtask:$
$0< t \leq 3$
$0<$ $n$ $\leq 10^3$
$0< a_i \leq 10^5$
$For$ $60$% $subtask:$
$0< t \leq 1$
$0<$ $n$ $\leq 5*10^6$
$0< a_i \leq 5*10^6$
保證所有$a_i$數字皆不相同(#2~#5測資點)
$For$ $100$% $subtask:$
$0< t \leq 3$
$0<$ $n$ $\leq 5*10^6$
$0< a_i \leq 10^9$
保證所有測資點中所有變數皆為正整數
8/22 12:38 測資補強
原初階班上學期期中考防破台
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||