ABC452E You WILL Like Sigma Problem

思路

利用 $i \bmod j = i - \lfloor \frac{i}{j} \rfloor \cdot j$ 将原式拆分为两部分：

$$ \text{Ans} = (\sum_{i=1}^N A_i \cdot i) \times (\sum_{j=1}^M B_j) - \sum_{j=1}^M (B_j \cdot j \cdot \sum_{i=1}^N A_i \cdot (\lfloor \frac{i}{j} \rfloor)) $$

第一部分：直接 $O(N+M)$ 计算。

第二部分：对于固定的 $j$，$\lfloor \frac{i}{j} \rfloor$ 的值呈块状分布，使用分块。利用 $A$ 的前缀和快速计算每一块内 $A_i$ 的和，乘上对应的商即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
const ll Mod=998244353;
ll n,m,a[500001],b[500001],p[500001];
int main(){
	cin>>n>>m;
	for(ll i=1;i<=n;i++)cin>>a[i];
	for(ll i=1;i<=m;i++)cin>>b[i];
	for(ll i=1;i<=n;i++)p[i]=(p[i-1]+a[i])%Mod;
	ll sumb=0,p1=0;
	for(ll i=1;i<=m;i++)sumb=(sumb+b[i])%Mod;
	for(ll i=1;i<=n;i++)p1=(p1+a[i]*i)%Mod;
	p1=p1*sumb%Mod;
	ll p2=0;
    for(ll j=1;j<=m;j++){
        ll sum=0;
        for(ll k=1;k*j<=n;k++){
            ll l=k*j;
            ll r=min(n,(k+1)*j-1);
            ll t=(p[r]-p[l-1]+Mod)%Mod;
            sum=(sum+k*t)%Mod;
        }
        p2=(p2+b[j]*j%Mod*sum)%Mod;
    }
    cout<<(p1-p2+Mod)%Mod;
}