(\)
除法分块
求以(N)为被除数，在([0,N])的范围内，将所得的商向下取整相同的所有除数区间。
- (Nin [0,10^9])
这个问题其实有( ext O(sqrt N))的解决方案，即除法分块。
我们先给出做法，在证明正确性和复杂度。
(\)
做法
维护两个变量(L,R)，代表当前除数区间为闭区间([L,R])，(L)初始值为(1)。
然后在(Lle N)时循环进行下面的过程：
- 设(t=lfloorfrac{N}{L} floor)
- 当前答案区间的右端点(R=lfloorfrac{N}{t} floor)
- (L=R+1)
(\)
正确性证明
开始时左端点是(1)显然是没有问题的，而以后的每一次操作(L=R+1)，因此，我们只需要证明每次的(R)都为正确的即可。
首先(lfloorfrac{N}{t} floor)一定是属于该除数区间的，所以我们只需要证明该数为区间上界。
反证法。设(X=lfloorfrac{N}{t} floor)不是我们想要得到的(R)，那么至少有(X+1)属于答案区间。
于是有(lfloorfrac{N}{X+1} floor=t)，因为是下取整，于是有(Nge t imes (X+1))，于是有(lfloorfrac{N}{t} floorgeig(lfloorfrac{t imes (X+1)}{t} floor=X+1ig))
而根据定义有(X=lfloorfrac{N}{t} floor)，于是有(Xge X+1)，与事实相悖。
(\)
复杂度证明
分情况讨论。
当所选除数(le sqrt N) 时，显然这一部分的除数区间不会超过(sqrt N) 个。
当所选除数(ge sqrt N)时，得到的商(le sqrt N)，商不超过(sqrt N)种，所以除数区间也不会超过(sqrt N)个。
于是总时间复杂度( ext O(sqrt N))。
(\)
(\)
一类求和式的推导
给出两个数列(A,B)和一个整数(N)，其中(A)的下标范围为([1,N])，(B)的下标范围为([0,N))
定义下表范围为([1,N])的数列(C)，试求出所有的(C_i)：(egin{align}C_i=sum_{j=1}^i A_{lfloorfrac{i}{j} floor} imes B_{i\%j}end{align})
- (Nin [1,10^5])
(\)
(Part 1: A_i=1,B_i=i)
(egin{align}C_i=sum_{j=1}^i A_{lfloorfrac{i}{j} floor} imes B_{i\%j}=sum_{j=1}^i A_{lfloorfrac{i}{j} floor} imes B_{i-lfloorfrac{i}{j} floor imes j}=sum_{j=1}^i ig(i-lfloorfrac{i}{j} floor imes jig)=sum_{j=1}^i i-sum_{j=1}^i lfloorfrac{i}{j} floor imes jend{align})
左一半求和为(i^2)
右一半求和时，考虑对于一个除法分块的区间([L,R])，这一段区间累加的答案为(t imes frac{(L+R)(R-L+1)}{2})
(\)
(Part 2: A_i=i,B_i=i)
(egin{align}C_i=sum_{j=1}^i A_{lfloorfrac{i}{j} floor} imes B_{i\%j}=sum_{j=1}^i lfloor frac i j floor imesig(i-lfloorfrac{i}{j} floor imes jig)=sum_{j=1}^i i imeslfloor frac i j floor -sum_{j=1}^i lfloorfrac{i}{j} floor^2 imes jend{align})
同样对一个除法分块的区间([L,R])考虑，左一半对答案的贡献为(t imes i imes (r-l+1))
右一半对答案的贡献为(t^2 imes frac{(L+R)(R-L+1)}{2})
(\)
(Part 3: A,B)随机
(egin{align}C_i=sum_{j=1}^i A_{lfloorfrac{i}{j} floor} imes B_{i\%j}=sum_{j=1}^i A_{lfloorfrac{i}{j} floor} imes B_{i-lfloorfrac{i}{j} floor imes j}end{align})
考虑一个除法分块的区间([L,R])对答案的贡献为(egin{align}sum_{j=L}^R A_{lfloorfrac{i}{j} floor} imes B_{i-lfloorfrac{i}{j} floor imes j}=A_{lfloorfrac{i}{j} floor} imes sum_{j=L}^R B_{i-lfloorfrac{i}{j} floor imes j}end{align})
于是左边的(A)数列的答案是固定的，右边的(B)数列的答案注意到可以表示成一个数列隔一段取一个数求和的形式。
于是(N^2)预处理(f[i][j])，表示从第(i)个位置开始（含第(i)个位置），向前每隔(j)个位置取一次的数求和，根据除法分块的定义，(i-t imes R)应该为可选择的最靠前的数字。于是对于一个除法分块的区间([L,R])，有(sum_{j=L}^R B_{i-t imes j}=f[i-t imes L][t])
(\)
(Code)
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 100100
#define mod 123456789
#define R register
#define gc getchar
using namespace std;
typedef long long ll;
inline ll rd(){
ll x=0; bool f=0; char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}
return f?-x:x;
}
ll n,a[N],b[N],c[N],f[N][350];
int main(){
n=rd();
for(R ll i=1;i<=n;++i) a[i]=rd();
for(R ll i=1;i<=n;++i) b[i-1]=rd();
for(R ll j=1;j<=340;++j)
for(R ll i=0;i<=n;++i) f[i][j]=((i>=j?f[i-j][j]:0)+b[i])%mod;
for(R ll i=1;i<=n;++i){
for(R ll j=1;j<=340&&j<=i;++j) (c[i]+=a[i/j]*b[i%j])%=mod;
for(R ll l=341,r;l<=i;l=r+1){
ll t=i/l; r=i/t;
(c[i]+=a[t]*f[i-t*l][t])%=mod;
}
printf("%lld
",c[i]);
}
return 0;
}