E-efficient.cc

#include <bits/stdc++.h>

using namespace std;

#define FOR(i,a,b) for (int i = int(a), _end_##i = int(b); i < _end_##i; ++i)
#define REP(i,n) FOR(i,0,n)

const int MOD = 998244353;

int Solve(int N, const vector<int> &A) {
  // 320 is the square root of 100,000 (the maximum possible value of A[i])
  // plus a few more to avoid off-by-one errors.
  vector<int> memo1(320);
  vector<int> memo2(320);
  auto Solve = [&](int i, int last_k, int last_val) {
    int k = (A[i - 1] + last_val - 1) / last_val;
    int val = A[i - 1] / k;
    return (int64_t{k - 1} * i + (k <= val ? memo1[k] : memo2[val]))%MOD;
  };

  int64_t total = 0;
  vector<int> new_memo1(320);
  vector<int> new_memo2(320);
  FOR(i, 1, N) {
    for (int k = 1; k*k <= A[i]; ++k) {
      new_memo1[k] = Solve(i, k, A[i] / k);
      new_memo2[k] = Solve(i, A[i] / k, k);
    }
    memo1.swap(new_memo1);
    memo2.swap(new_memo2);
    total += memo1[1];
  }
  return total % MOD;
}

int main() {
  // Make C++ I/O not slow. It's sad that this is necessary :-(
  ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

  int T = 0;
  cin >> T;
  REP(_, T) {
    int N = 0;
    cin >> N;
    vector<int> A(N);
    for (int &i : A) cin >> i;
    cout << Solve(N, A) << '\n';
  }
}