需要背诵的模板

FFT

CPP

void fft(complex *a,int n)
{
	for(int i=0;i<n;i++)
		if(r[i]>i)
			swap(a[i],a[r[i]]);
	for(int len=2,m=1;len<=n;m=len,len<<=1)
	{
		complex W=complex{cos(pi/m),sin(pi/m)},w=complex{1.0,0.0};
		for(int l=0,r=len-1;r<=n;l+=len,r+=len)
		{
			complex w0=w;
			for(int p=l,lim=l+m;p<lim;p++)
			{
				complex x=a[p]+w0*a[p+m],y=a[p]-w0*a[p+m];
				a[p]=x,a[p+m]=y;
				w0=w0*W;
			}
		}
	}
}

f(n)=\sum_{d|n}g(d)

\begin{align}\notag\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j) \text{ is prime}] &= \sum_{d \in \text{prime}} \sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[gcd(i,j)=1]\end{align}

\begin{align}\notag\sum_{i=1}^n\text{lcm}(i,n) &= \sum_{i=1}^{n}\frac{in}{\gcd(i,n)}\\&=\notag\sum_{d|n}^n\sum_{i=1}^{\frac{n}{d}}[\gcd(i,\frac{n}{d})=1]in\\&=\notag\sum_{d|n}^{n}n\sum_{i=1}^{\frac{n}{d}}\end{align}

。

[~~全篇背诵并默写~~]

文章操作

相关推荐

评论

需要背诵的模板