NOIp总复习—联赛常用数学知识与代码模板【持续更新】

再怎么说数学也是联赛可能考的大头项目。

吃了数学的亏而丢分是非常惨的orz

(本文将以各类数学方法最简单的代码打法为主,讲解为辅。)


欧拉筛

  • 用于筛出1到LIM的所有质数。并保存了每个数的最小质因数
#define LIM 100000
ll pms[100010],pt=0,vstd[100010];
void euler(){
    for (Rint i=2;i<=LIM;i++){
        if(!vstd[i])pms[++pt]=i,vstd[i]=i;
        for (Rint j=1;j<=pt&&pms[j]*i<=LIM;j++){
            vstd[i*pms[j]]=pms[j];
            if(i%pms[j]==0)break;
        }
    }
}

分解质因数

O(log n)方法,需要先用欧拉筛进行预处理。

ll fcts[100010],ft=0;
void pfct_logn(ll u){
    while(u>1){
        fcts[++ft]=vstd[u];
        while(vstd[u]==fcts[ft])
            u/=vstd[u];
    }
    if(u>1)
        fcts[++ft]=u;
}

O(√n)方法,可用于极大数。

void pfct_sqrtn(ll u){
    for (Rint i=2;i*i<=u;i++){
        if(u%i==0)fcts[++ft]=i;
        while(u%i==0)u/=i;
    } 
    if(u>1)
        fcts[++ft]=u;
}

统计质因数

倍数法,用于统计长数列中gcd为u的数对个数或gcd不同值的个数。

  • 其中f(u)代表gcd正好为u的个数,g(u)代表gcd是u的倍数的个数。则f(i)=g(i)-f(2i)-f(3i)-f(4*i)….
  • 开始可用桶来统计个数。
ll a[100010],b[100010],d1[100010],d2[100010],f[100010],g[100010],cnt1[100010],cnt2[100010];
int solve(int l1,int r1,int l2,int r2){
    for (Rint i=l1;i<=r1;i++)
        cnt1[a[i]]++;
    for (Rint i=l2;i<=r2;i++)
        cnt2[b[i]]++;
    for (Rint i=1;i<LIM;i++)
        for (Rint j=i;j<LIM;j+=i)
            d1[i]+=cnt1[j];
    for (Rint i=1;i<LIM;i++)
        for (Rint j=i;j<LIM;j+=i)
            d2[i]+=cnt2[j];
    int res=0;
    for (Rint i=1;i<LIM;i++)
        g[i]=1ll*d1[i]*d2[i];
    for (Rint i=LIM-1;i>=1;i--){
        f[i]=g[i];
        for (Rint j=2*i;j<LIM;j+=i)
            f[i]-=f[j];
        if (f[i]) res++;
    }
    return res;
}

获取因数

试除法,用于单个数。O(√n)

vector<ll> v[100010];
void fct_sqrtn(ll u){
    for (Rint i=1;i*i<=u;i++)
        if(u%i==0){
            v[u].push_back(i);
            if(u/i!=i)v[u].push_back(u/i);
        }
}

倍数法,用于获得1到n所有数因数。O(n log n)

void allfct_nlogn(ll u){
    for (Rint i=1;i<=u;i++)
        for (Rint j=1;j<=u/i;j++)
            v[i*j].push_back(i);
}

欧几里得算法

  • 求两数最大公约数
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}

拓展欧几里得算法

  • a*x+b*y=gcd(a,b) 的一组特殊解
  • x的最小解为 (x%b+b)%b
  • 另外的,若想获得 a*x+b*y=c 的解,则需要先保证 gcd(a,b)|c方程的一组解x_0=x*c/gcd(a,b),y_0=y*c/gcd(a,b)
  • 而上述方程的最小解(x0%d)+d)%(b/d) d=a/gcd(a,b)
  • 返回值为两数最大公约数
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    ll r=exgcd(b,a%b,y,x);
    y-=x*(a/b);
    return r;
}

整除分块

  • 用于计算 \Sigma_{i=1}^{n}\frac{n}{i}
ll sum_frac(ll u){
    ll res=0;
    for (ll l=1,r;l<=u;l=r+1){
        r=u/(u/l);
        res+=(r-l+1)*(u/l);
    }
    return res;
}

秦九韶算法

  • 用于计算高次方程对某数取模的结果
ll as[110]={0,1,2,3,4},nx=4;
ll qin_jiu_shao(ll x,ll P){
    ll res=as[nx]%P;
    for (Rint i=nx-1;i>=0;i--)
        res=(res*x%P+as[i])%P;
    return res;
}

快速幂取模

ll pw(ll a,ll x,ll P){
    ll res=1;
    while(x){
        if(x&1)res=res*a%P;
        a=a*a%P;
        x>>=1;
    }
    return res;
}

防溢乘法取模

  • 与快速幂大同小异。
ll mult(ll a,ll b,ll P){
    ll res=0;
    while(b){
        if(b&1)res=(res+a)%P;
        a=(a<<1)%P;
        b>>=1;
    }
    return res;
}

欧拉函数

线性求1到n欧拉函数。改进于欧拉筛

ll phi[100010];
void phi_all(ll n){
    phi[1]=1;
    for (Rint i=2;i<=LIM;i++){
        if(!vstd[i])pms[++pt]=i,phi[i]=i-1;
        for (Rint j=1;j<=pt&&pms[j]*i<=LIM;j++){
            vstd[i*pms[j]]=true;
            if(i%pms[j]==0){
                phi[i*pms[j]]=phi[i]*pms[j];
            }else phi[i*pms[j]]=phi[i]*phi[pms[j]];
        }
    }
}

求单个数的欧拉函数

ll phi_of(ll x){
    euler(),pfct_logn(x);//或者pfct_nsqrtn(x)
    ll phix=x;
    for (Rint i=1;i<=ft;i++)
        phix=phix*(fcts[i]-1)/fcts[i];
    return phix; 
}

求1到n-1中的与n互质数的总和

ll sum_of_mq(ll x){
    return x*phi_of(x)/2;
}

求a^x模P的结果,x非常大。

ll pw2(ll a,ll x,ll P){
    return pw(a,x%phi[P],...);//a,P互质
    return pw(a,x%phi[P]+phi[P],...)//a,P不互质 
}

乘法逆元

线性求1到n所有数模质数p的逆元

ll inv[100010];
void get_inv(ll n,ll P){
    inv[0]=inv[1]=1;
    for (Rint i=2;i<=n;i++)
        inv[i]=(P-P/i)*inv[P%i]%P;
} 

求单个数模质数p的逆元。

ll inv_of(ll u,ll P){
    return pw(u,P-2,P);
}

卢卡斯定理

  • 用于求解组合数  C_a^b 质数p取模的结果。
ll fac[1000100];
void lucas_init(ll p){
    get_inv(1000000,p);
    fac[0]=fac[1]=1;
    for (Rint i=1;i<=1000000;i++)
        fac[i]=fac[i-1]*i%p,
        inv[i]=(inv[i-1]*inv[i])%p;
}
ll lucas(ll a,ll b,ll p){
    if(a<b)return 0;
    if(a<p)return fac[a]*inv[b]%p*inv[a-b]%p;
    return lucas(a/p,b/p,p)*lucas(a%p,b%p,p)%p;
}

中国剩余定理

  • 用于求解同余方程组x同余ri(mod ai),其中所有模数两两互质
ll n,a[1000000],r[1000000];
ll crt(){
    ll M=1,Mi,x1,y1;
    for (Rint i=1;i<=n;i++)
        M*=a[i];
    ll res=0;
    for (Rint i=1;i<=n;i++){
        Mi=M/a[i];
        exgcd(Mi,a[i],x1,y1);
        res=(res+Mi*x1*r[i])%M;
    }
    return res;
}

拓展中国剩余定理

  • 用于求解同余方程组x同余ri(mod ai),其中所有模数不一定互质
ll excrt(){
    ll x=r[1],m=a[1],x1,y1;
    for (Rint i=2;i<=n;i++){
        ll z=((r[i]-x)%a[i]+a[i])%a[i];
        ll gd=exgcd(m,a[i],x1,y1),m0=m/gd*a[i];
        if(z%gd)return -1;
        x1=mult(x1,z/gd,a[i]/gd);
        x=(mult(m,x1,m0)+x)%m0;
        m=m0;
    }
    return x;
}

矩阵快速幂

  • 线性递推方程加速。
  • 代码为斐波那契数列模板。
#include <bits/stdc++.h>
using namespace std;
#define Rint register int
typedef long long ll;
typedef long long mat[2][2];
const ll MOD=10000;
mat src={1,1,1,0},res={1,0,0,1},t={0,0,0,0};
inline void mult(mat &a,mat &b){
    memset(t,0,sizeof(t));
    for (Rint i=0;i<2;i++)
        for (Rint j=0;j<2;j++)
            for (Rint k=0;k<2;k++)
                t[i][j]+=a[i][k]*b[k][j]%MOD,
                t[i][j]%=MOD;
    for (Rint i=0;i<2;i++)
        for (Rint j=0;j<2;j++)
            a[i][j]=t[i][j];
}
ll pw(ll u){
    res[0][0]=res[1][1]=1;
    res[0][1]=res[1][0]=0;
    src[0][0]=src[0][1]=src[1][0]=1;
    src[1][1]=0;
    while(u){
        if(u&1)mult(res,src);
        mult(src,src);
        u>>=1;
    }
    return (res[0][1]+res[0][0])%MOD;
}
int main(){
    ll n;
    while(cin>>n){
        if(!~n)break;
        if(n==0)puts("0");
        else if(n==1)puts("1");
        else cout<<pw(n-2)<<'\n';
    }
    return 0;
} 

发表评论

电子邮件地址不会被公开。 必填项已用*标注