Loading...

数论板子小结

check评论:0 条 remove_red_eye浏览量:61 change_historyTags:默认分类
作者 : Decoration date_range日期 : 2018-11-06

快速幂:

int ksm(long long qaq,int b)
{
    long long res=1;
    while(b)
    {
        if(b&1)
        {
            res=res*qaq;
        }
        qaq*=qaq;
        b>>=1;
    }
    return res;
}

线性筛欧拉函数&&质数&&莫比乌斯函数:

void euler()
{
    phi[1]=1;
    for(int i=2;i<maxn;i++)
    {
        if(!vis[i])
        {
            prime[++cnt]=i;
            phi[i]=i-1;
            mu[i]=-1;
        }
        for(int j=1;j<=cnt,i*prime[j]<maxn;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else
            {
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
            mu[i*prime[j]]=-mu[i];
        }
    }
} 

线性求逆元:

for(int i=2;i<=n;i++)
{
    inv[i]=(ll)(p-p/i)*inv[p%i]%p;
    printf("%d\n",inv[i]);
}

$exgcd$:

void exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return ;
    }
    exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-(a/b)*y;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名