考察

以下では \(\lfloor i/j \rfloor\) で「\(i\) を \(j\) で割ったときの商」を表します．

\(j, k\) を固定したとき，\(\lfloor i/j \rfloor = k\) となる \(i\) は \(jk \leq i \leq \min(j(k+1) - 1,\ N)\) の範囲です．この範囲において，\((i \bmod j) = i - jk\) が成り立つので，

\[ A_i \cdot B_j \cdot (i \bmod j) = B_j \cdot (A_i \cdot i) - B_j \cdot (A_i \cdot jk)\]

と変形できます．

上の式の範囲内の総和を求めることを考えたとき，第 \(1\) 項は範囲内の \(A_i \cdot i\) の総和を \(B_j\) 倍すれば，第 \(2\) 項は範囲内の \(A_i\) の総和を \(jkB_j\) 倍すれば得られます．これらはどちらも累積和によって \(O(N)\) 時間で前計算でき，質問ごとに \(O(1)\) 時間で得られます．

特定の \(j\) に対して，\(k\) がとり得る値は \(1\) 以上 \(\lfloor N/j \rfloor\) 以下です．よって，ありうる \((j, k)\) の組の個数は \(\frac{N}{1} + \frac{N}{2} + \cdots + \frac{N}{N}\) 以下です．これは \(O(N \log N)\) のオーダーであることが知られています(調和数)．

全体で \(O(N \log N)\) 時間で動き，十分高速です．

実装例 (C++)

#include <iostream>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
#include <vector>
using std::vector;
using std::pair;
using std::make_pair;
using std::min;

typedef long long int ll;

#include <atcoder/modint>
using mint = atcoder::modint998244353;

ll n, m;
vector<mint> a, b;

void solve () {
	// line up their indexs
	a.insert(a.begin(), 0);
	n++;
	b.insert(b.begin(), 0);
	m++;

	// sum[i]  := sum_{k < i} a[k] * 1
	// sum2[i] := sum_{k < i} a[k] * k
	vector<mint> sum(n+1, 0), sum2(n+1, 0);
	for (ll i = 0; i < n; i++) {
		sum[ i+1] = sum[ i] + a[i] * 1;
		sum2[i+1] = sum2[i] + a[i] * i;
	}

	mint ans = 0;
	for (ll bi = 1; bi < m; bi++) {
		mint bans = 0;
		for (ll i = 0; i * bi < n; i++) {
			ll l = (i+0) * bi;
			ll r = min((i+1) * bi, n);

			// sum_{l <= k < r} a[k] * (k - i*bi)
			bans += (sum2[r] - sum2[l]);
			bans -= (sum[r] - sum[l]) * (i*bi);
		}
		ans += bans * b[bi];
	}

	cout << ans.val() << "\n";
}

int main (void) {
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);

	cin >> n >> m;
	
	a.resize(n);
	for (ll i = 0; i < n; i++) {
		ll x; cin >> x;
		a[i] = x;
	}
	b.resize(m);
	for (ll i = 0; i < m; i++) {
		ll x; cin >> x;
		b[i] = x;
	}

	solve();

	return 0;
}