E
对于 \(i\mod j\) ，有一个经典的转化： \(i \mod j =i- \lfloor \frac{i}{j} \rfloor \times j\) 。
代入题目中的算式
\[\sum_{i=1}^n \sum_{j=1}^m a_i \times b_j-\sum_{i=1}^n\sum_{j=1}^m a_i \times b_j \times \lfloor \frac{i}{j} \rfloor \times j
\]
第一个式子很简单。难办的是第二个式子的快速求解。
枚举 \(i,j\) ,太慢。令 \(k=\lfloor \frac{i}{j} \rfloor\) ，如果我们枚举 \(j,k\) ，则可确定 \(i\) 的范围： \([k\times j,j\times (k+1)-1]\) 。
对于每对 \((j,k)\) ，对答案的贡献为 \(b_j \times j \times k\times\sum_{i=k \times j}^{j \times (k+1)-1} a_i\) ，对 \(a\) 使用前缀和即可。
那这样枚举会不会TLE呢？看上去要枚举两维，是二次方复杂度，但事实上，其实际复杂度为 \(O(\sum_{i=1}^n\frac{n}{i})\) ，由调和级数，即为 \(O(n \log n)\) 。
abc452_e
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define int long long
#define eb emplace_back
using namespace std;const int N=5e5+10, lxy=998244353;
int a[N], b[N], s[N];
int n,m,ans;signed main(){cin.tie(0)->sync_with_stdio(0);cin>>n>>m;for(int i=1; i<=n; i++) cin>>a[i], s[i]=s[i-1]+a[i], s[i]%=lxy;int sum=0;for(int i=1; i<=m; i++) cin>>b[i], sum+=b[i];for(int i=1; i<=n; i++)ans+=a[i]*sum%lxy*i%lxy, ans%=lxy;for(int j=1; j<=m; j++)for(int k=1; k*j<=n; k++){int l=k*j, r=min(n,j*(k+1)-1);// 有可能超过n，所以取一个minans-=b[j]*k%lxy*j%lxy*(s[r]-s[l-1])%lxy; ans%=lxy;}cout<<(ans%lxy+lxy)%lxy;return 0;
}