Codeforces Round 910 (Div. 2) B. Milena and Admirer
思路：
要使数组非递减，则可以先进行倒序遍历，对于当前的 \(a_i\) , 要使 \(a_i\le a_{i+1}\)
我们可以进行贪心，让 \(a_i\) 分完尽可能使每个 \(a_i / k \le a_{i+1}\)
因此 k 为 \(a_i / a_{i+1}\) 上取整 ， \(a_i\) 更新为 \(a_i / k\)
ans += k - 1 ( 分为 k 份 ， 即划分 k-1 次 )
#define int long long
#define LL long long
#define ld long double
#define fr(i,l,r) for(int i=l;i<=r;i++)
#define rf(i,r,l) for(int i=r;i>=l;i--)
#define ppb pop_back()
#define pb push_back
#define pf push_front
#define so(a) sort(a.begin(),a.end())
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define ikun ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(0)
//mp.reserve(1024);
//mp.max_load_factor(0.25);
//auto check = [&]()->bool
// {
//
// };
using namespace std;
const int N = 2e5 + 10;
int n;
int a[N];
int k;
signed main()
{
ikun;
int t;
t = 1;
cin >> t;
auto solve = [&]()->void
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
int ans = 0;
for (int i = n - 1; i >= 1; i--)
{
k = (a[i] + a[i + 1] - 1) / a[i + 1];
//cout << "k: " << k << endl;
a[i] = a[i] / k;
ans += k - 1;
}
cout << ans << endl;
};
while (t--)
{
solve();
}
return 0;
}