自动搬运

查看原文

来自洛谷，原作者为

	Amidst 生若直木，不语斧凿。

搬运于2025-08-24 23:14:35，当前版本为作者最后更新于2025-04-29 10:10:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

思路

考虑每条满足 $xy$ 为完全平方数的边 $(x,y)$，其贡献都为 $1$，考虑设计一种母函数区分边权为 $0$ 和 $1$ 带来的贡献，不妨令

$$f_i=\sum\limits_{1\le j < i} [\sqrt{ij} \in \mathbb Z] $$

即 $f_i$ 表示小于 $i$ 的数中与 $i$ 相乘能得到完全平方数的数的个数。

则显然有一种母函数的设计

$$F(i)=f_ix+i-f_i-1$$

即自己不能给自己带来贡献，$f_i$ 带来 $1$ 的贡献，$i-f_i-1$ 的部分带来 $0$ 的贡献。

于是可以列出答案的母函数

$$F_{ans}(n)=\prod\limits_{i=2}^n F(i)$$

观察这个形式，由母函数的定义及基本性质可以得到

$$ans_i=[x^i]F_{ans}(n)$$

于是考虑 $f$ 怎么求。利用惊人的注意力可以发现这是个积性函数，欧拉筛预处理即可。

我们利用分治思想和 FFT 求出 $F_{ans}(n)$（可能是一种分治 FFT？）。

考虑时间复杂度，利用 Master 定理，

$$T(n)=2T(\frac{n}{2})+O(n\log n)=O(n^{\log_22}\log^{1+1}n)=O(n\log^2n) $$

注意常数优化。

代码

卷积长度不要太大。

#include <bits/stdc++.h>
//#include <bits/extc++.h>
namespace fastio
{
#ifdef ONLINE_JUDGE
	namespace __getchar
	{
		char buf[1<<24],*p1=buf,*p2=buf;
		inline char getchar() {return (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2))?EOF:(*p1++);}
	}
	using __getchar::getchar;
#endif
	inline int read(int &x) {unsigned s=0;int f=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-f; ch=getchar();} while(isdigit(ch)) {s=(s<<3)+(s<<1)+(ch^48); ch=getchar();} return x=s*f;}
	inline unsigned read(unsigned &x) {unsigned s=0; char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) {s=(s<<3)+(s<<1)+(ch^48); ch=getchar();} return x=s;}
	inline long long read(long long &x) {unsigned long long s=0; long long f=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-f; ch=getchar();} while(isdigit(ch)) {s=(s<<3)+(s<<1)+(ch^48); ch=getchar();} return x=s*f;}
	inline unsigned long long read(unsigned long long &x) {unsigned long long s=0; char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) {s=(s<<3)+(s<<1)+(ch^48); ch=getchar();} return x=s;}
	inline char read(char &x) {x=getchar(); while(x=='\0'||x=='\r'||x=='\n'||x==' ') x=getchar(); return x;}
	inline int read(char *x) {int i=0; char ch=getchar(); while(ch=='\0'||ch=='\r'||ch=='\n'||ch==' ') ch=getchar(); while(ch!='\0'&&ch!='\r'&&ch!='\n'&&ch!=' '&&ch!=EOF) {x[i++]=ch; ch=getchar();} x[i]='\0'; return i;}
	inline int read(std::string &x) {x=""; int i=0; char ch=getchar(); while(ch=='\0'||ch=='\r'||ch=='\n'||ch==' ') ch=getchar(); while(ch!='\0'&&ch!='\r'&&ch!='\n'&&ch!=' '&&ch!=EOF) {x+=ch; i++; ch=getchar();} return i;}
	inline void write(int x) {if(x<0) {putchar('-'); write(0-x/10); putchar(48-x%10); return;} if(x<10) putchar(x+48); else {write(x/10); putchar(x%10+48);}}
	inline void write(unsigned x) {if(x<10) putchar(x+48); else {write(x/10); putchar(x%10+48);}}
	inline void write(long long x) {if(x<0) {putchar('-'); write(0-x/10); putchar(48-x%10); return;} if(x<10) putchar(x+48); else {write(x/10); putchar(x%10+48);}}
	inline void write(unsigned long long x) {if(x<10) putchar(x+48); else {write(x/10); putchar(x%10+48);}}
	inline void write(char x) {putchar(x);}
	inline void write(char *x) {char *tmp=x; while(*x!=EOF&&*x!='\0') putchar(*x++); x=tmp;}
	inline void write(const char *x) {while(*x!=EOF&&*x!='\0') putchar(*x++);}
	inline void write(std::string x) {for(char c:x) putchar(c);}
	template<typename _Tp,typename ...Args>
	inline void read(_Tp &x,Args &...args) {read(x); read(args...);}
	template<typename _Tp>
	inline void read(std::initializer_list<_Tp> &x) {for(auto i:x) read(i);}
	template<typename _Tp,typename ...Args>
	inline void write(_Tp x,Args ...args) {write(x); write(args...);}
	template<typename _Tp>
	inline void write(std::initializer_list<_Tp> x) {for(auto i:x) write(i);};
}
using namespace fastio;
//#define int long long
#define G 3
#define mod 998244353
#define __BEGIN_MULTITEST__ \
	signed T; \
	scanf("%d",&T); \
	while(T--) \
	{
#define __END_MULTITEST__ }
using namespace std;
//using namespace __gnu_cxx;
//using namespace __gnu_pbds;
namespace ntt
{
	inline int quick_pow(int a,int b)
	{
		int ret=1;
		while(b)
		{
			if(b&1)
				ret=1ll*ret*a%mod;
			a=1ll*a*a%mod;
			b>>=1;
		}
		return ret; 
	}
	int g[1100005],invlim[1100005];
	void initNTT(int lim)
	{
		g[0]=1;
		g[1]=quick_pow(G,(mod-1)/lim);
		for(int i=2;i<=lim;i++)
			g[i]=1ll*g[i-1]*g[1]%mod;
	}
	void initinv(int lim)
	{
		invlim[0]=invlim[1]=1;
		invlim[2]=499122177;
		for(int i=4;i<=lim;i<<=1)
			invlim[i]=1ll*invlim[i>>1]*invlim[2]%mod;
	}
	void NTT(int f[],int rev[],int lim,int type)
	{
		if(!lim) return;
		for(int i=0;i<=lim;i++)
			if(i<rev[i])
				swap(f[i],f[rev[i]]);
		for(int k=1,tmp=lim>>1;k<lim;k<<=1,tmp>>=1)
			for(int i=0;i<lim;i+=(k<<1))
				for(int j=0,s=0;j<k;j++,s+=tmp)
				{
					int x=f[i|j],y=1ll*g[s]*f[i|j|k]%mod;
					f[i|j]=(x+y)%mod;
					f[i|j|k]=(x-y+mod)%mod;
				}
		if(type==-1)
		{
			f[0]=1ll*f[0]*invlim[lim]%mod;
			for(int i=1;i<=(lim>>1);i++)
			{
				f[i]=1ll*f[i]*invlim[lim]%mod;
				if(i!=(lim>>1))
				{
					f[lim-i]=1ll*f[lim-i]*invlim[lim]%mod;
					swap(f[i],f[lim-i]);
				}
			}
		}
	}
}
namespace sieve
{
	int f[300005],p[300005];
	bool np[300005];
	void Euler(int n)
	{
		int cnt=0;
		np[1]=f[1]=1;
		for(int i=2;i<=n;i++)
		{
			if(!np[i])
			{
				p[++cnt]=i;
				f[i]=1;
			}
			for(int j=1;j<=cnt&&i*p[j]<=n;j++)
			{
				np[i*p[j]]=1;
				if(i%p[j]==0)
				{
					f[i*p[j]]=f[i/p[j]]*p[j];
					break;
				}
				f[i*p[j]]=f[i]*f[p[j]];
			}
		}
		for(int i=1;i<=n;i++)
			f[i]--;
	}
}
using namespace ntt;
using namespace sieve;
int tmp[524289],tmpb[524289],rev[524289];
int lenans=0;
namespace cdqfft
{
	void Multiply(int tmp[],int tmpb[],int rev[],int lim)
	{
		if(lim<=32)
		{
			int res[33]={0};
			for(int i=0;i<=lim&&tmp[i];i++)
				for(int j=0;j<=lim&&tmpb[j];j++)
					res[i+j]=(res[i+j]+1ll*tmp[i]*tmpb[j]%mod)%mod;
			memcpy(tmp,res,sizeof(int)*33);
			return;
		}
		initNTT(lim);
		NTT(tmp,rev,lim,1);
		NTT(tmpb,rev,lim,1);
		for(int i=0;i<=lim;i++)
			tmp[i]=1ll*tmp[i]*tmpb[i]%mod;
		NTT(tmp,rev,lim,-1);
	}
	void cdqFFT(int l,int r,int lim,int L)
	{
		if(l==r)
		{
			tmp[0]=l-f[l]-1;
			tmp[1]=f[l];
			if(f[l])
				lenans++;
			return;
		}
		int mid=l+r>>1;
		memset(tmp,0,sizeof(int)*(lim+1));
		const int N=lim+1;
		int *tmpc=new int[N];
		memcpy(tmpc,tmpb,sizeof(int)*(lim+1));
		cdqFFT(l,mid,lim>>1,L-1);
		memcpy(tmpb,tmp,sizeof(int)*(lim+1));
		memset(tmp,0,sizeof(int)*(lim+1));
		cdqFFT(mid+1,r,lim>>1,L-1);
		for(int i=0;i<=lim;i++)
			rev[i]=(rev[i>>1]>>1)|((i&1)<<L);
		Multiply(tmp,tmpb,rev,lim);
		memcpy(tmpb,tmpc,sizeof(int)*(lim+1));
		delete tmpc;
	}
}
int n;
using namespace cdqfft;
signed main()
{
//	__BEGIN_MULTITEST__
#ifndef ONLINE_JUDGE
	freopen("P12321.in","r",stdin);
	freopen("P12321.out","w",stdout);
#endif
	read(n);
	if(n==1)
		return 0*printf("1\n");
	Euler(n);
	int lim=1,L=-1,len=n;
	while(lim<len)
	{
		lim<<=1;
		L++;
	}
	initinv(lim);
	cdqFFT(2,n,lim,L);
	for(int i=0;i<n;i++)
		write(tmp[i],'\n');
//	__END_MULTITEST__
	return 0;
}