Description：

给出数组 $a$ 和 $b$ ，求数组 $c$ ：

$$\begin{align}c_i=\sum_{j=1}^ia_{\lfloor \frac i j\rfloor}b_{i\text{ mod }j}\end{align}$ $

$1\le n \le 100000$

Solution：

首先把 $j$ 按照 $\le \sqrt n$ 和 $>\sqrt n$ 分类，对于 $\le \sqrt n$ 的数，直接枚举 $j$ 暴力计算，复杂度 $O(n\sqrt n)$ ，对于 $>\sqrt n$ 的 $j$ ，把原式化成 $\begin{align}\sum_{j>\sqrt i}a_{\lfloor\frac i j\rfloor}b_{i-\lfloor\frac i j\rfloor\times j}\end{align}$ ，这个可以除法分块，由于除法分块要求区间和，所以要求出 $\begin{align}f[i][j]=\sum b_{i-k\times j}\end{align}$ ，这个可以预处理。那么此时 $\begin{align}\sum_{k=l}^rb_{i-\lfloor\frac i l\rfloor\times k}=f[i-\lfloor\frac i l\rfloor\times l][\lfloor\frac i l\rfloor]-f[i-\lfloor\frac i l\rfloor\times (r+1)][\lfloor\frac i l\rfloor]\end{align}$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

typedef long long ll;

ll a[MAXN],b[MAXN],c[MAXN];

#define MOD 123456789

int k = 330;

ll f[MAXN][330];

int main()

{

	freopen("mmt.in","r",stdin);

	freopen("mmt.out","w",stdout);

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%lld",&a[i]);

	for(int i = 0;i < n;++i)scanf("%lld",&b[i]);

	memset(f,0,sizeof(f));

	for(int i = 0;i < n;++i)

		for(int j = 1;j < k;++j)

			f[i][j] = ((i >= j ? f[i - j][j] : 0) + b[i]) % MOD;

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= k && j <= i;++j)

			c[i] = (c[i] + a[i / j] * b[i % j] % MOD) % MOD;

	for(int i = 1;i <= n;++i)

	{

		for(int l = k + 1,r = 0;l <= i;l = r + 1)

		{

			r = i / (i / l);

			c[i] = (c[i] + (a[i / l] * (f[i - i / l * l][i / l] - (i - (i / l) * (r + 1) >= 0 ? f[i - (i / l) * (r + 1)][i / l] : 0) + MOD) % MOD) % MOD) % MOD;

		}

	}

	for(int i = 1;i <= n;++i)printf("%lld\n",c[i]);

	return 0;

}