基础数论略讲

基础数论略讲

基础数论算法
首先,它们这些算法十分基础,基础到并不包含莫比乌斯反演什么的,所以仅仅当做娱乐性质的文章

内容一览
由于数论中的算法较多,下面先进行一个小汇总

素数的筛法

最大公约数求法

扩展GCDGCD算法

质因数分解法

乘法逆元求法

组合数计算方法

LucasLucas定理

中国剩余定理

线性一次同余式解法

等比数列求和(当然这应该不是数论)

当然啦,都是一些比较基础的东西,意思是需要数学基础的东西

下面将进行逐个讲解

详解
素数的筛法
原理
我们很多时候用的是朴素的质数筛法,即我们按照2到nn进行筛去,记录一个visvis数组表示当前数是否为质数即可

代码
1
但是还有一种O(n)O(n)的方法,即欧拉筛法,每次让每一个数只被它所含有的最小的质因子筛去,详情见代码

代码
void construct_prime_table(LL range){

    for(LL i=2;i<range;i++){

        if(!vis[i])pt[cnt++]=i;
        for(int j=0;j<cnt;j++){

            if(i*pt[j]>=range)break;
            vis[i*pt[j]]=1;
            if(i%pt[j]==0)break;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
最大公约数(GCD)
原理
这个东西其实非常简单啦,我们可以使用辗转相除法或是更相减损法,但是下面只贴辗转相除法的代码,而更相减损法也有它的用武之地,那就是在求两个巨大的高精度数的时候,用于SteinStein算法,其他文章会予以介绍

下面贴代码

代码
LL gcd(LL x,LL y){

   if(y==0)return x;
   return gcd(y,x%y);
}
1
2
3
4
扩展GCD算法
原理
主要是来源于数论中的裴蜀定理,然后思路与原GCD十分相近,可以求出使得

ax+by=gcd(x,y)ax+by=gcd(x,y)
成立且|a|+|b||a|+|b|最小的一组解(a,b)(a,b)
下面贴代码

代码
void patulous_gcd(LL a,LL b,LL& d,LL& x,LL& y){

    if(b==0){d=a;x=1;y=0;return;}
    patulous_gcd(b,a%b,d,y,x);y-=a/b*x;
}
1
2
3
4
质因数分解法
原理
这里介绍朴素的算法,即O(n−−√)O(n)的那个,虽然有更先进的算法,但是我并不会,下面直接贴代码

代码
void prime_factorization(LL x){

    for(LL i=2;i<=(LL)sqrt(x);i++){

        if(vis[i]||x%i!=0)continue;
        mod[size]=1;
        while(x>1&&x%i==0){

            mod[size]*=i;
            x=x/i;
        }
        size++;
    }
    if(x>1)mod[size++]=x;
}
1
2
3
4
5
6
7
8
9
10
11
12
乘法逆元的求法
原理
我们可以用一种神奇的方式来以O(M)O(M)的复杂度生成一个模数M(为质数)的所有逆元,考虑这样的式子:

ax+b≡0(modM)ax+b≡0(modM)(注意那个是同余符号)

等式左右同时乘以 x−1b−1x−1b−1,则有

a∗b−1+x−1≡0(modM)a∗b−1+x−1≡0(modM)
即 x−1≡−a∗b−1(modM)x−1≡−a∗b−1(modM)
这样我们就成功地求出了xx的模MM意义下的逆元

代码如下

代码
void get_all_multiplicative_inverse(LL M){

    inv[1]=1;
    for(LL i=2;i<M;i++){

        inv[i]=(M+(-(M/i)*inv[M%i])%M)%M;
    }
}
1
2
3
4
5
6
原理
但是如果我们只想要一个逆元怎么办?

我们可以考虑如下同余式:

aa−1≡1(modM)aa−1≡1(modM)
即有a∗a−1+b∗M=1a∗a−1+b∗M=1 (注意这个时候是等于号)

这样,我们便可以使用扩展GCD啦

代码
LL get_single_multiplicative_inverse(LL a,LL M){

    LL d,x,y;
    patulous_gcd(a,M,d,x,y);
    return (x%M+M)%M;
}
1
2
3
4
5
组合数计算方法
原理
大家应该都知道组合数是怎么算的,然而那个除来除去的部分我们都很讨厌,所以我们可以使用逆元来搞定它,即乘上这个数的逆元模MM等于除以这个数模MM
代码
LL calculate_combination_number(LL m,LL n,LL k){

    if(m<n)return 0;
    LL ans=1;
    //get_all_multiplicative_inverse(k);
    for(LL i=1;i<=n;i++){

        ans=(ans*(inv[i]*(i+m-n))%k)%k;
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
LucasLucas定理
原理
就是这样的一个小式子:

(百度百科直下)

直接贴代码

代码
LL Lucas(LL m,LL n,LL k){

    if(m<k&&n<k){

        return calculate_combination_number(m,n,k);
    }
    return (Lucas(m/k,n/k,k)*Lucas(m%k,n%k,k))%k;
}
1
2
3
4
5
6
线性同余式解法
原理
就是考虑如下的一个式子:

ax≡b(modM)ax≡b(modM)
我们只要等式两端同乘a−1a−1即可

即x≡a−1b(modM)x≡a−1b(modM)
下面贴代码

代码
LL solve_congruence(LL a,LL b,LL m){

    LL _a=get_single_multiplicative_inverse(a,m);
    return (b*_a)%m;
}
1
2
3
4
中国剩余定理
原理
额。。。写这文章简直是要累死啦。。。 
就是说现在我们手头有一组线性同余式,它们的模数都是互质的,我们要求这个方程组的解,那么我们可以使用中国剩余定理,它常常被用于模数不是质数的情况,这个时候我们就需要用中国剩余定理来求出答案

大致是这样的:

真是服了这个markdown里似是非是的Latex了,根本打不出来上面的好吗

然后,我们可以很轻松的发现:

是唯一解,这个只要有点数学基础的应该都会证(但是我不会)

这样就搞定啦O(∩_∩)O

下面是代码

代码
LL chinese_remainder_theorem(LL x){

    LL ans=0;
    prime_factorization(M);
    calculate_array_a();//计算a数组
    ans=(((M/mod[i]*a[i]*get_single_multiplicative_inverse(M/mod[i],mod[i]))%M+ans)%M+M)%M;
    }
    return ans;
}

等比数列求和
原理
应该都会吧,是吧= =

代码
LL calculate_geometric_progression(LL first,LL ratio,LL num){

    return (((get_power(ratio,num+1)-1)*inv[ratio-1])%M*first)%M;
}

其中getget_power()power()用于求幂
 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114869.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • kafka和rabbitmq和activemq区别_kafka消息持久化处理

    kafka和rabbitmq和activemq区别_kafka消息持久化处理一、语言不同RabbitMQ是由内在高并发的erlanng语言开发,用在实时的对可靠性要求比较高的消息传递上。kafka是采用Scala语言开发,它主要用于处理活跃的流式数据,大数据量的数据处理上二、结构不同RabbitMQ采用AMQP(AdvancedMessageQueuingProtocol,高级消息队列协议)是一个进程间传递异步消息的网络协议RabbitMQ…

    2022年10月28日
  • Nexus 3的搭建和简单使用介绍

    搭建Nexus 3私服一、简介nexus 私服间于本地仓库和中央仓库直接。1、有两种安装方式:使用tomcat启动,Tgz使用自带的Jetty启动 ,zip包(推荐使用)2、下载地址 : Nexus oss3、环境准备: jdk8+ + maven3+二、安装步骤1、windos上安装– nexus 2.x 版本1、将bin添加到环境变量中,nexus2、修改/bin…

  • 正则表达式Python_js正则表达式实例

    正则表达式Python_js正则表达式实例正则表达式详解正则表达式英文名称叫RegularExpression简称RegEx,是用来匹配字符的一种工具,它常被用在网页爬虫,文稿整理,数据筛选等方面,最常用的就是用在网页爬虫,数据抓取。一、正则表达式的各种符号解释(来自维基百科)~~~是不是感觉太多了,因此我将常用的整理出来了二、进行逐个详解1.首先导入模块importre2.匹配多种可能使用[]…

  • Java-MD5加密[通俗易懂]

    Java-MD5加密[通俗易懂]密码全是明文,防止内部人员监守自盗,改成暗文密码加密一般使用MD5加密特点:一旦加密之后,就不可解密光是MD5加密还不够安全,这时候就要添加盐值:盐值作用:让你的密码更加安全,MD5:支持加密次数MD5加密三个概念:MD5常规加密,为了让你的密码更加安全,MD5加密还要加盐值,为了让你的密码超级安全,它支持加密次数MD5Utils.encrypByMd5(String类型的密码)就执行加密importjava.security.MessageDigest;impo

  • 手把手教你使用R语言做LASSO 回归

    手把手教你使用R语言做LASSO 回归LASSO回归也叫套索回归,是通过生成一个惩罚函数是回归模型中的变量系数进行压缩,达到防止过度拟合,解决严重共线性的问题,LASSO回归最先由英国人RobertTibshirani提出,目前在预测模型中应用非常广泛。在新格兰文献中,有大牛提出,对于变量过多而且变量数较少的模型拟合,首先要考虑使用LASSO惩罚函数。今天我们来讲讲怎么使用R语言通过LASSO回归构造预测模型。首先我们要下载R的glmnet包,由LASSO回归的发明人,斯坦福统计学家TrevorHastie领衔开发。加载

  • 实战模拟│JWT 登录认证「建议收藏」

    实战模拟│JWT 登录认证「建议收藏」分布式跨域认证的解决新方案

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号