数学相关内容总结

筛法

有待填坑

莫比乌斯反演

基本定义

若定义

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

,则有f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})

其中,\mu(d)称为莫比乌斯函数，其值为

\mu(d)=1,d=1\mu(d)=(-1)^r,d=\Pi_{i=1}^rp_i

其余情况下\mu(d)=0

基本性质

性质1

\sum_{d|n}\mu(d)=0，d\geq1

证明：

考虑d中的质数个数，仅需计算其函数值不为0的情况即可

则有\sum_{d|n}\mu(d)=\sum_{i=2_p}^nC_n^i-\sum_{i=2p-1}^nC_n^i=(1-1)^n=0

性质2

莫比乌斯函数为积性函数

证明：|\frac{n}{d}}f(d)=\sum_{d|n}f(d)\sum_{d|\frac{n}{d`}}\mu(d)=f(n)$$

例题

有待填坑

杜教筛

可以用来求积性函数在10^{10}左右的前缀和。

首先定义Dirichlet卷积：

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

令l(n)=(f * g)(n),再定义F(x),G(x),L(x)为以上三个函数的前缀和，则有

L(n)-g(1)F(n)=\sum_{i=2}^{n}g(i)F(\lfloor \frac{n}{i}\rfloor)

例题

[51NOD]莫比乌斯函数之和

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<cmath>
#define N 7000000
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

LL x,y,n,size;
bool flag[N+10];
int mu[N+10],p[700000];
int sum[N+10];
LL a[500010],b[500010];

inline int Abs(int x){return (x<0)?-x:x;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline void Ready(){
    LL i=0,j=0,x=0;
    mu[1]=1;
    for (i=2;i<=N;i++){
        if (!flag[i])   {mu[i]=-1;  p[++p[0]]=i;}
        for (j=i*i;j<=N;j+=i)   flag[j]=1;
        for (j=1;j<=p[0];j++){
            if (i*p[j]>N)   break;
            if (i%p[j]) mu[i*p[j]]=-mu[i];
            else {
                mu[i*p[j]]=0;   break;
            }
        }
    }
    for (i=1;i<=N;i++)  sum[i]=sum[i-1]+mu[i];
}

inline LL &ID(LL x){
    return (x<=size)?a[x]:b[n/x];
}

inline LL Cal(LL x){
    LL i=0,cnt=1,l=0;
    if (x<=N)   return sum[x];
    LL &y=ID(x);
    if (y!=a[0])    return y;
    for (i=2;i<=x;i=l+1){
        l=x/(x/i);
        cnt-=(l+1-i)*Cal(x/i);
    }
    return y=cnt;
}

inline LL Work(LL x){
    if (x<=N)   return sum[x];
    size=(int)sqrt(x);  n=x;
    memset(a,-23333,sizeof(a)); memset(b,-23333,sizeof(b));
    return Cal(x);
}

int main(){
    scanf("%lld%lld",&x,&y);
    Ready();
    cout<<Work(y)-Work(x-1)<<endl;
    return 0;
}

未完待续

FFT&NTT

原理

对于形如y_n=\sum x_ih_{n-i}的式子，称为y对xh的卷积。

定义多项式A(x)=\sum_{i=0}^{n-1} a_{i}x^i

这种表示法称为系数表示法。由拉格朗日插值法可知，一个n次多项式可以通过n+1个点唯一确定。这种表示法称为点值表示法。

FFT进行多项式乘法运算的原理为，首先将系数表示法转化为点值表示法，然后在线性时间内计算出新的多项式的点值表示法，再转化回系数表示法。其核心部分在于如何快速实现两种表示法的转换。

首先定义主n次单位根：\omega_n=e^{\frac{2\pi i}{n}}

对于单位根，有如下三个引理：

1.消去引理

\omega_{dn}^{dk}=\omega_n^k

证明：写成指数形式即可证明

2.折半引理

当n为偶数时，n个n次单位根平方的集合等于n/2个n/2次单位根平方的集合

证明：

(\omega_n^{k})^2=\omega_{\frac{n}{2}}^k

(\omega_n^{k+\frac{n}{2}})^2=\omega_n^{2k+n}=\omega_n^n\omega_{\frac{n}{2}}^k=\omega_{\frac{n}{2}}^k

3.求和引理

对于不能被n整除的整数k，有

\sum_{j=0}^{n-1}(\omega_n^k)^j=0

证明：

由几何级数的求和公式易证。

由秦九韶公式可知，对于一个n次多项式求单点的值，时间复杂度为线性的。为了将系数表示法转化为点值表示法，需要n+1个点的值。总的时间内复杂度变为了平方级。FFT的核心思想便是利用n次单位根的性质，将这一过程优化到O(nlogn)