mmt

居然第一步膜化乘除 都没看出来，没救了...

大概是贡献前缀和优化的做法

大家都学会了么？

咱发现有大量的 (i/j , i%j ) 同时 对很多 c 产生了贡献，咱可以去优化这一部分的转移，具体做法就是根据前面能加的后面也能加，然后一路累加且算贡献

对于小于根号的所有 i/j ，咱可以优化这一部分转移，然后对于大于根号的 i/j ，暴力算就好了，两者复杂度都是是 n 根号 n 的

//by Judge
#include<bits/stdc++.h>
#define Rg register
#define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(Rg int i=(a),I=(b)-1;i>I;--i)
#define ll long long
#define eps 1e-8
using namespace std;
const int mod=123456789;
const int M=1e5+3;
typedef int arr[M];
#ifndef Judge
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
char buf[1<<21],*p1=buf,*p2=buf;
inline int read(){ int x=0,f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
} char sr[1<<21],z[20];int CCF=-1,Z;
inline void Ot(){fwrite(sr,1,CCF+1,stdout),CCF=-1;}
inline void print(int x,char chr='\n'){
    if(CCF>1<<20)Ot();if(x<0)sr[++CCF]=45,x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++CCF]=z[Z],--Z);sr[++CCF]=chr;
} int n,bl; arr a,b,c; double inv[M];
#define Div(x,y) (int(x*inv[y]+eps))
int main(){ n=read(),bl=sqrt(n);
    fp(i,1,n) inv[i]=1.0/i,a[i]=read(); fp(i,0,n-1) b[i]=read();
    fp(x,1,bl) fp(y,0,x-1){ Rg ll now=-1; Rg int A,l,r; // i/j = x 步长 ， y 初始位置 
        for(Rg int k=x+y;k<=n;k+=x) if(Div(k,Div(k,x))==x){ // 必须是可达状态 ，此时 j = k/x 
            if(now<0) l=r=Div(k,x),A=k%r,now=1ll*a[x]*b[A]%mod;
            else{ ++r; if(Div(k,l)!=i) ++l; else A=k%l,now=(now+1ll*a[x]*b[A])%mod; }
            c[k]=(c[k]+now)%mod; // 当前的 now 存在的之前的状态当前 k 也可达 
        }
    }
    fp(i,1,n) fp(j,1,i) if(Div(i,j)<=bl) break;
        else c[i]=(c[i]+1ll*a[Div(i,j)]*b[i%j]%mod)%mod;
    fp(i,1,n) print(c[i]); return Ot(),0;
}