C++(clang++11) 解法, 执行用时: 1124ms, 内存消耗: 61620K, 提交时间: 2021-05-04 10:57:40

#include<bits/stdc++.h>
using namespace std;
typedef vector<int> poly;
const int mod=998244353,g=3,invg=(mod+1)/3;
int a[600005],b[600005],c[600005],n,wk[20][600005],wk2[20][600005],tr[600005],ta[600005],tb[600005];
poly s[600005];
int Power(int x,int y){
	int r=1;
	while(y){
		if(y&1)r=1ll*r*x%mod;
		y>>=1,x=1ll*x*x%mod;
	}
	return r;
}
void GetTr(int l){
	for(int i=0;i<l;i++)tr[i]=((tr[i>>1]>>1)|(i%2?(l>>1):0));
}
void NTT(int *a,int n,int flag){
	for(int i=0;i<n;i++)if(i<tr[i])swap(a[i],a[tr[i]]);
	for(int i=1,t=1;i<n;i<<=1,t++){
		for(int j=0;j<n;j+=(i<<1)){
			for(int k=0;k<i;k++){
				int x=a[j+k],y;
				if(flag==1)y=1ll*a[i+j+k]*wk[t][k]%mod;
				else y=1ll*a[i+j+k]*wk2[t][k]%mod;
				a[j+k]=(x+y)%mod,a[i+j+k]=(x-y+mod)%mod;
			}
		}
	}
	if(flag==-1)for(int i=0,u=Power(n,mod-2);i<n;i++)a[i]=1ll*a[i]*u%mod;
}
poly Multi(const poly &a,const poly &b){
	poly ret;
	ret.resize(a.size()+b.size()-1);
	int len=1;
	while(len<ret.size())len<<=1;
	GetTr(len);
	for(int i=0;i<len;i++)ta[i]=tb[i]=0;
	for(int i=0;i<a.size();i++)ta[i]=a[i];
	for(int i=0;i<b.size();i++)tb[i]=b[i];
	NTT(ta,len,1),NTT(tb,len,1);
	for(int i=0;i<len;i++)ta[i]=1ll*ta[i]*tb[i]%mod;
	NTT(ta,len,-1);
	for(int i=0;i<ret.size();i++)ret[i]=ta[i];
	return ret;
}
int main(){
	for(int i=1;i<=19;i++){
		int w=Power(g,(mod-1)/(1<<i));
		for(int j=0,u=1;j<(1<<i-1);j++,u=1ll*u*w%mod)wk[i][j]=u;
		w=Power(invg,(mod-1)/(1<<i));
		for(int j=0,u=1;j<(1<<i-1);j++,u=1ll*u*w%mod)wk2[i][j]=u;
	}
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)scanf("%d",&b[i]);
	for(int i=n;i>=1;i--){
		vector<int> tmpa,tmpb;
		tmpa.push_back(0),tmpb.push_back(0);
		for(int j=i;j<=n;j+=i)tmpa.push_back(a[j]),tmpb.push_back(b[j]);
		s[i]=Multi(tmpa,tmpb);
		for(int j=2*i;j<=n;j+=i)for(int k=1;k<s[j].size();k++)s[i][k*(j/i)]=(s[i][k*(j/i)]-s[j][k]+mod)%mod;
		for(int j=1;j<s[i].size();j++)c[i*(j+1)]=(c[i*(j+1)]+s[i][j])%mod;
	}
	for(int i=1;i<=3*n;i++)cout<<c[i]<<' ';
	return 0;
}