加入收藏
首页 > 生活 >

数论-同余与扩展欧几里得详解(附例题及代码)

2023-08-21 23:13:50 来源：博客园 小 中

数论-同余与扩展欧几里得详解(附例题及代码)

注意:这篇文章的信息量会有一点多，请耐心看完

一.同余

1.1 同余的定义

给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)

简单来说，对于x,y，若x%p=y%p，即x,y对于p的余数相同，则称为同余


(资料图)

1.2 同余的性质

本身不重要，但我们可恶的教练让我们背下来

于是摆烂…………………………

实在是不想码出来(懒)

二.求解乘法逆元

2.1费马小定理(很费马)

2.1.1费马小定理简介

假设a是一个整数，p是一个质数，则有以下定理

\(a^{p-1}\)≡1(mod p)

证明方法：出门左转，百度（点击有惊喜）欢迎您

2.1.2费马小定理求解逆元

p为质数，则有\(a^{p-1}\)≡1(mod p)

则不难推出:\(a^{p-2}\)*a≡1(mod p)

所以，\(a^{p-2}\)就是a再在%p意义下的逆元

2.2欧拉定理

2.2.1欧拉定理简介

\(a^{φ(p)}\)≡1(mod p)(即为费马小定理的一般形式)

φ(p)为欧拉函数，不清楚的请出门左转见百度

2.2.2费马小定理求解逆元

推理:\(a^{φ(p)-1}\)*a≡1(mod p)

所以\(a^{φ(p)-1}\)就是a在%p意义下的逆元

2.2.3代码实现

long long ksm(long a,long p,long long mod){//快速幂 long long t=1,x=a%mod;while(p){if(p&1) t=t*x%mod;x=x*x%mod;p>>1;}return t;  }  long long getinv(long long a,long long mod){//inv一般表示逆元 return ksm(a,mod-2,mod);   }

2.3递推求解逆元(相信你十分了解递推)

2.3.1推理过程

p为模数，a为待求逆元(先设出来)，所以\(a^{-1}\)是a在模p意义下的逆元

p=k*a+r(k为常数，r为p/a的余数->r

则k=[p/a]，r=p%a

k*a+r≡0 (mod p)

此时，两边同除ar，得

k*\(r^{-1}\)+\(a^{-1}\)≡0(mod p)

\(a^{-1}\)≡-k*\(r^{-1}\)(mod p)

inv(a)≡-[p/a]*inv(p%a) (mod p)

以inv(1)==1 作为边界，开始递推

2.3.2代码实现

void getinv(long long mod){inv[1]=1;//边界条件for(int i=2;i

2.4扩展欧几里得算法求逆元

2.4.1 前置知识-裴蜀定理(贝祖定理)

说明了对任何整数a、b和它们的最大公约数d

关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数

特别地，一定存在整数x,y，使ax+by=d成立

它的一个重要推论是：a,b互质的充分必要条件是存在整数x,y使ax+by=1.

由此，我们便可对式子进行化简

将同余式ax≡c(mod b)转化为ax+by=c(很重要，做题列方程化简几乎必定会用到，牢记)

2.4.2小知识-充要条件

充分必要条件也即充要条件，意思是说，如果能从命题p推出命题q，而且也能从命题q推出命题p ，则称p是q的充分必要条件，且q也是p的充分必要条件。

样例：

1 A=“三角形的三条边都相等”；B=“三角形的三个角都相等”。

A是B的充分必要条件；

2 A=“某人触犯了法律”；B=“应当依照刑法对他处以刑罚”。

A是B的必要不充分条件；（A触犯法律包含各种法，有刑法有民法；B已经确定是刑法。B属于A所以A是B的必要不充分条件）

3 A=“付了足够的钱”；B=“买到商店里的东西”。

A是B的必要不充分条件；（ A付够了钱 可以买的是车、房子等；但是B能买到商店里的东西一定是要付够钱）

2.4.3扩展欧几里德算法—求最小整数解推导

ax1+by1=gcd(a,b)　　　ax2+by2=gcd(a,b)

可由此推出

ax1+by1=ax2+by2

a(x1-x2)=b(y2-y1)

因为gcd(a,b)为a,b的最大公因数，所以将 A=a/gcd(a,b)，B=b/gcd(a,b)，向下推出

A(x1-x2)=B(y2-y1)

此时A，B互质，继续向下推出

A(nB)=B(nA)

(x1-x2)=n*B

(y2-y1)=n*A

重点部分

这里从x入手，得

(x1-x2)=n*B

x1=x2+n*B

由此，我们推出了x解的通解公式 x=x0+n*B

同理，我们推出了y解的通解公式 y=y0-m*A

如果要求x的最小整数解,即x0,就为x0=x%B

如果我们要求的是 ax+by=c，还得先转化 x=x*c/gcd(a,b).

然后套入公式

B=b/gcd(a,b)

x0=x%(b/gcd(a,b))

证毕(博主已累成狗，点个推荐呗) 若还不清楚，可移步Ta的博客(讲的蛮详细的)

2.4.4扩展欧几里德算法—代码实现

int exgcd(int a,int b,int &x,int &y){if(b==0){x=1,y=1;return a;}int gcd=exgcd(b,a%b,y,x);//没错，这玩意能求gcd    //不过c++是有系统函数求GCD的->__gcd(a,b);y-=a/b*x;return gcd;  }

2.4.4扩展欧几里德算法—应用场景

(1).求解不定方程

(2).求解线性不定方程(线性同余方程)

(3).求解模的逆元

2.4.5扩展欧几里德算法—逆元求解

int exgcd(int a,int b,int &x,int &y){if(b==0){x=1,y=1;return a;}int gcd=exgcd(b,a%b,y,x);y-=a/b*x;return gcd;  }  int getinv(int a,int p){int x,y,gcd;gcd=exgcd(a,p,x,y);if(gcd==1){x=(x%p+p)%p;return x;}else{cout<<"a,p不互质"<

三.例题

3.1「NOIP2012」同余方程

思路:使用欧几里德扩展进行求解->模板题

代码如下

#include  #define int long long  using namespace std;  int x=0,y=0;  int exgcd(int a,int b,int &x,int &y){if(b==0){x=1;y=0;return a;}int g=exgcd(b,a%b,y,x);y-=a/b*x;return g;  }  signed main(){int a,b;cin>>a>>b;exgcd(a,b,x,y);cout<<(x%b+b)%b;return 0;  }

后续还会有数论的题解更新，敬请期待

关键词：

相关新闻

资讯

昂立教育(600661.SH)：上半年净亏损1.08亿元
昂立教育(600661.SH)：上半年净亏损1.08亿元

格隆汇8月21日丨昂立教育(600661 SH)公布2023年半年......更多>

宋亚轩 小短文②“不完美暗恋”
宋亚轩 小短文②“不完美暗恋”

仅哔哩哔哩更新两章完第二章宋亚轩视角我喜欢了5年的......更多>

E起见证！传祺E9成为河南第十四届运动会开幕式官方指定用车
E起见证！传祺E9成为河南第十四届运动会开幕式官方指定用车

8月18日晚，隋唐洛阳城国家遗址公园应天门再次成为世......更多>

《应变求新，韧性生长 2023中国消费品牌增长峰会成功举办》
《应变求新，韧性生长 2023中国消费品牌增长峰会成功举办》

8月17日，由第一财经、第一财经商业数据中心（CBNData......更多>

央行公布8月LPR报价，1年期下降10个基点
央行公布8月LPR报价，1年期下降10个基点

8月21日，中国人民银行授权全国银行间同业拆借中心公......更多>

湖南2023高职专科批(职高对口类)第二次征集志愿国家任务计划(湖南2023高职专科投档线)
湖南2023高职专科批(职高对口类)第二次征集志愿国家任务计划(湖南2023高职专科投档线)

《湖南省2023年普通高校招生高职专科批(职高对口类)第......更多>

宁波：“免申即转”，一站式办理医保转移
宁波：“免申即转”，一站式办理医保转移

解决省内医保转移接续中的“痛点”（副题）宁波日报讯......更多>

张庭夫妇成立餐饮公司，继传销风波后又有新动作
张庭夫妇成立餐饮公司，继传销风波后又有新动作

第一财经消息，此前因为涉嫌传销而多次冲上热搜的演员......更多>

万达地产于黄石成立建设管理公司，注册资本1000万元
万达地产于黄石成立建设管理公司，注册资本1000万元

乐居财经刘治颖8月21日，万达地产集团有限公司新增投......更多>

小米Redmi 12新增4GB+128GB版本 949元起
小米Redmi 12新增4GB+128GB版本 949元起

近日，Redmi12手机新增了4GB+128GB版本，售价从原来的......更多>

关注

桐城农商银行：三个“着力”推进生源地信用助学贷款工作
桐城农商银行：三个“着力”推进生源地信用助学贷款工作
作为土生土长的法人金融机构，桐城农商银行扎根县域、... 更多>
桐城农商银行：三个“着力”推进生源地信用助学贷款工作
作为土生土长的法人金融机构，桐城农商银行扎根县域、... 更多>
洛浦街社卫中心中医技术治好街坊多年顽疾，患者直呼“真神奇”！
近日，家住洛浦街的胡先生经中医适宜技术“火龙罐”治... 更多>
啄木鸟投诉平台周报：培训机构收费“跑路”？ 警惕“零成本入门跨境电商”的虚假宣传
上周(2023年8月14日至8月20日)，中国网旗下啄木鸟投诉... 更多>
日经股指上涨
日经股指8月21日走高。日经225种股票平均价格指数收盘... 更多>
宁波慈溪市首届“青蓝企业家”沙龙举行
8月20日，宁波慈溪市举行首届“青蓝企业家”沙龙，旨... 更多>
广州市体育节丨城市CTT乒乓球积分联赛（第三站）圆满举行
日前，由广州市体育局、广州市体育总会主办，广州市乒... 更多>
549户摇号，广州市城隽雅苑北区共有产权住房选房顺序已定
8月18日下午，广州城投住房租赁发展投资有限公司在城... 更多>
安德斯特助力2023PEL夏季赛圆满落幕！长沙TEC斩获夏决总冠军！
明星选手华傲天，世界拳王邹市明也在空投之夜化身“精... 更多>
港元拆息全线下跌 三个月跌穿5%创逾两个月新低
智通财经APP获悉8月22日香港银行公会发布数据显示港元... 更多>
韩国票房：《奥本海默》位列票房榜首位
韩联社消息，据韩国电影票综合电算网8月21日发布的统... 更多>
多地市场监管部门公开征集线索，已有民众打举报电话
“关于征集医药领域商业贿赂问题线索的公告发布后，已... 更多>
国台办：海关总署决定暂停台湾地区芒果输入大陆
国台办发言人朱凤莲8月21日表示，今年以来，大陆海关... 更多>