ABC452E：原来是我们最喜欢的数学题！
Pure_ManaWing
·
·
题解
一眼整除分块吧，但最后为啥又不是了。
把原式的 i\bmod j 换掉，得
\sum_{i=1}^{n}\sum_{j=1}^{m}A_i\times B_j\times (i-j\times \lfloor\frac{i}{j}\rfloor)
乘法分配律拆括号，得
\sum_{i=1}^n\sum_{j=1}^{m} (A_i\times B_j\times i)-\sum_{i=1}^n\sum_{j=1}^{m} (A_i\times B_j\times j\times \lfloor\frac{i}{j}\rfloor)
这里我们想把 A_i\times B_i 拆掉。前面这个双重求和我们注意到其实有一个引理可以去掉：对于 a_1b_1+a_1b_2+a_2b_1+a_2b_2 可以提公因式得 a_1(b_1+b_2)+a_2(b_1+b_2)=(a_1+a_2)(b_1+b_2)。
这个结论可以推广到任意长度的数组，所以我们尝试拆掉，得
\underbrace{(\sum_{i=1}^{n}A_i\times i)(\sum_{j=1}^m B_j)}_{S_1}-\underbrace{\sum_{j=1}^{m}(B_j\times j\times\sum_{i=1}^nA_i\times \lfloor\frac{i}{j}\rfloor)}_{S_2}
- 当 $k=0$ 时，$i\in[1,\operatorname{min}(j-1,n)]$。
- 当 $k>0$ 时，$i\in[k\times j,\operatorname{min}(j\times k+j-1,n)]$。
容易发现记每个区间的左右端点分别为 $l,r$，那一个区间和就是 $k\sum_{i=l}^{r}A_i$。如果用前缀和维护，就可以 $\operatorname{O}(1)$ 解决每个区间。只要枚举每个 $k$ 即可得到结果，每一个 $j$ 需要循环 $\lfloor \frac{n}{j}\rfloor$ 次。
总时间复杂度即 $\operatorname{O}(\sum_{j=1}^m\lfloor\frac{n}{j}\rfloor)$，用调和级数计算可约等于 $\operatorname{O}(n\operatorname{log}n)$，足够通过本题。
在上面的计算的时候，不要忘记取模。
需要我直接给你解决这道题目的数学公式吗？
:::info[如果需要]
贴心的 PMW 帮你总结出了解决这道题目的数学公式。其中数组 $f$ 表示数组 $a$ 的前缀和。
$$\boxed{(\sum_{i=1}^{n}A_ii)(\sum_{j=1}^{m}B_j)-\sum_{j=1}^{m}(B_jj\times \sum_{k=1}^{\lfloor\frac{n}{j}\rfloor}k(f_{\operatorname{min}(j\times (k+1)-1,N)}-f_{jk-1}))}$$
注意到 $k=0$ 时对结果没有贡献，所以 $k$ 从 $1$ 开始。
:::
:::info[code]
```cpp
//#pragma GCC optimize("O3")
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define is insert
#define fr(i,a,b) for(int i=(a);i<=(b);i++)
#define rf(i,a,b) for(int i=(a);i>=(b);i++)
#define pri priority_queue
#define gYES printf("YES\n")
#define gNO printf("NO\n")
#define gYes printf("Yes\n")
#define gNo printf("No\n")
const int MOD=998244353;
const int Mod=1e9+7;
const int N=5e5;
using namespace std;
int max(int ax,int ay){ return (ax>ay)?ax:ay; }
int min(int ax,int ay){ return (ax<ay)?ax:ay; }
int abss(int ax){ return max(ax,-ax); }
void fastIO(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0); }
int n,m,a[N+5],b[N+5],f[N+5],s1,s2;
signed main(){
fastIO();
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> a[i]; s1=(s1+a[i]*i)%MOD;
f[i]=(f[i-1]+a[i])%MOD;
}
for(int i=1;i<=m;i++){
cin >> b[i];
s2=(s2+b[i])%MOD;
}s1=s1*s2%MOD;
for(int j=1;j<=m;j++){
s2=0;
for(int k=1;k<=n/j;k++){
s2=(s2+k*(f[min(j*(k+1)-1,n)]-f[j*k-1]))%MOD;
}s2=s2*(b[j]*j%MOD)%MOD;
s1=(s1-s2)%MOD;
}s1=(s1%MOD+MOD)%MOD;
cout << s1;
return 0;
}
```
:::