C++ 解法, 执行用时: 2453ms, 内存消耗: 41892K, 提交时间: 2021-12-18 20:44:13

#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#else
#define D(...) ((void)0)
//#define NDEBUG
#endif
#include<bits/stdc++.h>
#define int long long
#define SZ(x) ((int)(x).size())
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
template<class T>void rd(T&x){int f=0,c;while(!isdigit(c=getchar()))f^=!(c^45);x=(c&15);while(isdigit(c=getchar()))x=x*10+(c&15);if(f)x=-x;}
template<class T>void pt(T x,int c=-1){if(x<0)putchar('-'),x=-x;if(x>9)pt(x/10);putchar(x%10+48);if(c!=-1)putchar(c);}
using LL=long long;
const int P=23068673;
int ad(int k1,int k2){return k1+=k2-P,k1+=k1>>31&P;}
int su(int k1,int k2){return k1-=k2,k1+=k1>>31&P;}
int mu(int k1,int k2){return 1LL*k1*k2%P;}
void uad(int&k1,int k2){k1+=k2-P,k1+=k1>>31&P;}
void usu(int&k1,int k2){k1-=k2,k1+=k1>>31&P;}
template<class... T>int ad(int k1,T... k2){return ad(k1,ad(k2...));}
template<class... T>int su(int k1,T... k2){return su(k1,ad(k2...));}
template<class... T>int mu(int k1,T... k2){return mu(k1,mu(k2...));}
template<class... T>void uad(int&k1,T... k2){return uad(k1,ad(k2...));}
template<class... T>void usu(int&k1,T... k2){return usu(k1,ad(k2...));}
int po(int k1,int k2){
	int k3=1;
	for(;k2;k2>>=1,k1=mu(k1,k1))if(k2&1)k3=mu(k3,k1);
	return k3;
}
int mod(LL x){
	return (x%P+P)%P;
}
const int G=38,iG=po(G,P-2);
void NTT(vector<int>&a,int g,int lim){
	a.resize(lim);
	for(int i=0,j=0;i<lim;++i){
		if(i<j)swap(a[i],a[j]);
		for(int k=lim>>1;(j^=k)<k;k>>=1);
	}
	vector<int>w(lim>>1);w[0]=1;
	for(int i=1;i<lim;i<<=1){
		int wn=po(g,(P-1)/(i<<1));
		for(int j=(i>>1)-1;j>0;--j)w[j<<1]=w[j];
		for(int j=1;j<i;j+=2)w[j]=mu(w[j-1],wn);
		for(int j=0;j<lim;j+=i<<1)
			for(int k=0;k<i;++k){
				int x=a[j+k],y=mu(a[i+j+k],w[k]);
				a[j+k]=ad(x,y),a[i+j+k]=su(x,y);
			}
	}
	if(g==iG)for(int i=0,I=po(lim,P-2);i<(int)a.size();++i)a[i]=mu(a[i],I);
}
vector<int>operator*(vector<int>a,vector<int>b){
	if(SZ(a)<=50&&SZ(b)<=50){
		vector<int>c(SZ(a)+SZ(b)-1);
		rep(i,0,SZ(a)-1)rep(j,0,SZ(b)-1)uad(c[i+j],mu(a[i],b[j]));
		return c;
	}
	int need=(int)a.size()+b.size()-1,lim=1;
	while(lim<=need)lim<<=1;
	NTT(a,G,lim),NTT(b,G,lim);
	for(int i=0;i<lim;++i)a[i]=mu(a[i],b[i]);
	NTT(a,iG,lim);
	return a.resize(need),a;
}
vector<int>operator+(vector<int>a,vector<int>b){
	if(a.size()<b.size()){
		for(int i=0;i<(int)a.size();++i)(b[i]+=a[i])%=P;
		return b;
	}else{
		for(int i=0;i<(int)b.size();++i)(a[i]+=b[i])%=P; 
		return a;
	}
}
vector<int>pinv(const vector<int>&a,int n=-1){
	if(n==-1)n=a.size();
	if(n==1)return vector<int>(1,po(a[0],P-2));
	vector<int>b=pinv(a,(n+1)>>1),tmp=vector<int>(a.begin(),a.begin()+n);
	int lim=1;
	while(lim<=n*2-2)lim<<=1;
	NTT(b,G,lim),NTT(tmp,G,lim);
	for(int i=0;i<lim;++i)b[i]=mu(su(2,mu(b[i],tmp[i])),b[i]);
	NTT(b,iG,lim);
	return b.resize(n),b;
}
int n;
vector<int>f;
LL m;
namespace siever{
	const int N=100005;
	typedef long long ll;
	int T,B,tot;
	int p[N];
	ll n,a[N<<1];
	int g[N<<1],h[N<<1],s1[N<<1],s2[N<<1];
	int get(LL x){return x<=B?x:tot-n/x+1;}
	void main(){
		B=sqrt(n);
		tot=0;
		for(LL i=1;i<=n;i=a[tot]+1)++tot,a[tot]=n/(n/i),g[tot]=mod(a[tot]-1),h[tot]=su(mu(mod(a[tot]),mod(a[tot]+1),(P+1)/2),1LL);
		*p=0;
		for(int i=2;i<=B;++i)if(g[i]!=g[i-1]){
			p[++*p]=i;
			LL sq=1ll*i*i;
			for(int j=tot;a[j]>=sq;--j){
				usu(g[j],su(g[get(a[j]/i)],g[i-1]));
				usu(h[j],mu(i,su(h[get(a[j]/i)],h[i-1])));
			}
		}
		for(int i=1;i<=tot;++i)usu(h[i],g[i]),g[i]=su(0,g[i]),s1[i]=h[i],s2[i]=g[i];
		for(int b=*p;b>=1;--b){
			LL sq=1ll*p[b]*p[b];
			for(int _=tot;a[_]>=sq;--_){
				for(ll f1=p[b]-1,pw=p[b];pw<=a[_]/p[b];f1=f1*p[b],pw=pw*p[b]){
					uad(s1[_],mu(f1,su(s1[get(a[_]/pw)],h[p[b]])),mu(f1,p[b]));
					// s2[_]+=f2*(s2[get(a[_]/pw)]-g[p[b]]);
				}
			}
		}
		// printf("%lld %lld\n",s1[tot]+1,s2[tot]+1);
	}
	int coef[N<<1];
	pair<vector<int>,vector<int> >prod(int l,int r){
		if(l==r){
			return make_pair(vector<int>{coef[l]},vector<int>{1,su(0,mod(m/a[l]))});
		}
		int mid=(l+r)>>1;
		auto U=prod(l,mid);
		auto V=prod(mid+1,r);
		return make_pair(U.first*V.second+U.second*V.first,U.second*V.second);
	}
	void sol(){
		rep(i,1,tot){
			coef[i]=i==1?1:su(s1[i],s1[i-1]);
			assert(coef[i]>=0);
		}
		vector<int>u,v;
		tie(u,v)=prod(1,tot);
		v.resize(::n+1);
		f=u*pinv(v);
		f.resize(::n+1);
	}
}
signed main(){
#ifdef xay5421
	freopen("a.in","r",stdin);
#endif
	rd(n),rd(m);
	siever::n=m;
	siever::main();
	siever::sol();
	int sum=0,sum_=0,m_=mod(m);
	rep(i,1,n){
		sum=ad(mu(sum,m_),f[i]);
		sum_=ad(mu(sum_,m_),mu(f[i],i));
		printf("%lld ",su(mu(sum,i+1),sum_));
	}
	return 0;
}