需要背诵的模板

· · 个人记录

::::info[FFT]

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;
            }
        }
    }
}

::::

::::info[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}

::::

::::success[。] [全篇背诵并默写] ::::