是不是比 F 难。

然后你们写数论分块干啥。

首先把式子里 AiA_i 提出来。

∑i=1NAi∑j=1MBj×(i mod j)\displaystyle \sum_{i=1}^{N} A_i \sum_{j=1}^{M} B_j \times (i \bmod j)

注意到每次 ii 加上 11 之后式子右边的 $ \sum_{j=1}^{M} B_j \times (i \bmod j)$ 很容易可以通过上一个状态转移过来，具体来说就是 所有 i+1i + 1 的因数 BiB_i 的贡献都会是 00，剩下的都会系数增加 11，又发现 NN 很小，所以可以预处理每个 ii 的因数，两秒轻松能过，然后一个一个推每个 BiB_i 的贡献，具体实现可以看代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
vector<int> d[500005];
void init(int n)
{
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
            d[j].push_back(i);
        }
    }
}
signed main()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1), b(m + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int cnt1 = 0, cnt2 = 0;
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
        cnt2 = (cnt2 + b[i]) % mod;
    }
    init(n);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        cnt1 = (cnt1 + cnt2 + mod) % mod; // 先假设全部系数都加上了1
        for (int j = 0; j < d[i].size(); j++) {
            if (d[i][j] > m) {
                continue;
            }
            cnt1 = (cnt1 - (d[i][j] * b[d[i][j]]) % mod + mod) % mod; // 去掉变成0的
        }
        ans = (ans + a[i] * cnt1) % mod;
    }
    cout << ans;
    return 0;
}