最新要闻
- 市文化馆广场舞将亮相表演
- 8月20日最佳情报|青山碧水风景如画!壹粉分享初秋美景获奖
- 别了,恒大
- 赤峰黄金上半年净利润3.12亿元 同比减少24.08%
- 数字化支撑区域教育教学评价改革
- 【研报掘金】市场空间广阔 复合铜箔望开始批量商业化应用
- 企退与事退抚恤金解析:生前养老金差距大,死后抚恤金不一样!
- 看过来!广西、广东、云南游客,免门票!
- 山东省社保待遇资格认证怎么认证?微信支付宝认证简单又方便!
- 什么?时尚名媛竟然还能“参与”造火箭!
- 新能源汽车L2辅助驾驶装车率已逼近40% 远高于燃油车
- 谨防二手车套路!男子付16800订金买二手凯迪拉克 结果却被骗
- 小米14 Ultra预计明年3月发布 IMEI数据库出现双版本
- 想买X5的等一等!新款国产X5即将发布 动力外观均有提升
- 皇帝请弟弟吃饭,倒杯毒酒说:祝你活千岁!弟弟回答9字保全性命
- 韩媒:韩网再现“杀人预告”,这次发帖人身份认证是警察
手机
确山县委书记深入基层调研乡村建设工作
中国民生银行海口分行落实“不动产证回家”专项行动
- 确山县委书记深入基层调研乡村建设工作
- 中国民生银行海口分行落实“不动产证回家”专项行动
- 重庆7月汽车销量同比增长9.4% 新能源汽车占比突破40%
- 中央气象台8月21日10时继续发布暴雨蓝色预警
- 东方创业(600278)8月21日主力资金净卖出566.97万元
- 日厚生劳动相称要就医药安保与印度合作,日媒炒“减少对华依赖”
家电
数论-同余与扩展欧几里得详解(附例题及代码)
数论-同余与扩展欧几里得详解(附例题及代码)
注意:这篇文章的信息量会有一点多,请耐心看完
一.同余
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 作为边界,开始递推 说明了对任何整数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(很重要,做题列方程化简几乎必定会用到,牢记) 充分必要条件也即充要条件,意思是说,如果能从命题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能买到商店里的东西一定是要付够钱) 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)) 证毕(博主已累成狗, (1).求解不定方程 (2).求解线性不定方程(线性同余方程) (3).求解模的逆元 思路:使用欧几里德扩展进行求解->模板题 代码如下 后续还会有数论的题解更新,敬请期待
关键词:
2.3.2代码实现
void getinv(long long mod){inv[1]=1;//边界条件for(int i=2;i
2.4扩展欧几里得算法求逆元
2.4.1 前置知识-裴蜀定理(贝祖定理)
2.4.2小知识-充要条件
2.4.3扩展欧几里德算法—求最小整数解推导
点个推荐呗) 若还不清楚,可移步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扩展欧几里德算法—应用场景
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
数论-同余与扩展欧几里得详解(附例题及代码)
津膜科技(300334)8月21日主力资金净卖出336.67万元
人民同泰(600829)8月21日主力资金净卖出3245.72万元
市文化馆广场舞将亮相表演
美亚柏科(300188)每日收评(08-21)
甘肃创翼检测科技有限公司粉尘爆炸测试仪设备采购项目中标公示
确山县委书记深入基层调研乡村建设工作
铁岭新城(000809)8月21日主力资金净卖出979.13万元
新学期宝安将从这八个方面做好准备!加速迈向教育强区
亚联发展(002316)8月21日主力资金净买入9117.56万元
城建设计(01599.HK)将于8月31日举行董事会会议以审批中期业绩
湖南绥宁卫健局回应“女卫生院长被举报婚内出轨”:属实,将立案审查
《幸运草的约定》全角色攻略 角色选项指南
N协昌董秘回复:公司功率芯片产品的下游应用主要包括电动车辆、电动工具、消费电子、家用电器等领域
中国民生银行海口分行落实“不动产证回家”专项行动
重庆7月汽车销量同比增长9.4% 新能源汽车占比突破40%
上海虹桥医院医生讲解鱼鳞病患者怎么护理
我毁坏我的结婚证是否犯法
8月20日最佳情报|青山碧水风景如画!壹粉分享初秋美景获奖
走进济宁,开启戏剧之旅!《人民日报》聚焦青年导演创作扶持计划第二季
港股异动丨爱高集团暴跌82%创历史新低,遭索偿共2520万元
国台办:海关总署决定暂停台湾地区芒果输入大陆
探西辽河文明 品中华文化韵味
2024款坦克300上市 19.98万元起/新增轻混动力
贝尔戈米:我不讨厌阿瑙 取代卢卡库和哲科并不容易
miss dior香水价格(miss dior)
场均24分被骂数据刷子,场均17分却成全明星!NBA最懂感恩的球员
别了,恒大
投教 | 什么是量化投资?
如今直上银河去古诗 如今直上银河去求下联
任天堂社长谈为何不去投资某些新兴技术:理念不同
蒋孔阳美学思想新释(关于蒋孔阳美学思想新释简述)
有个罕见反转出现
金山桥街道开展交通安全警示宣传教育活动
全省首座区县级智慧水质监测实验室在无锡高新区投用
亚太股市收盘涨跌互现,日经225指数涨0.37%,新西兰NZX50指数跌1.31%
31999元!钱江QJ推出挎斗版300cc摩托车
力克英格兰 西班牙登顶女足世界杯
赤峰黄金上半年净利润3.12亿元 同比减少24.08%
广州市从化区总工会助千名职工圆梦大学
保卫萝卜4周赛8.21攻略2023
魏跟郭姓男孩取名 魏姓男孩起名宜用字
街舞达人起舞意风区
年轻人坐高铁跨省存钱,“特种兵式”存钱模式已经流行起来了吗?
数字化支撑区域教育教学评价改革
小米14 Ultra预计明年3月发布 IMEI数据库出现双版本
被贯通录取还能上北京私立高中吗?学籍能转到私立高中吗?
旅行集章 从“打卡”到催生城市美学文化盛景
跨界进行时,酒企争当“斜杠青年”
超百亿!深圳多金融机构减免支付手续费,降小微企业、商户经营成本
数字化支撑区域教育教学评价改革
【研报掘金】市场空间广阔 复合铜箔望开始批量商业化应用
英诺激光:公司暂未开展氢能源领域的业务
天风证券孔蓉:港股目前估值性价比较高 建议投资者加大关注
格力落榜500强 网友力撑董明珠
国台办:海关总署决定自即日起暂停台湾地区芒果输入大陆
为了让商家赚钱,支付宝到底有多拼
百公里仅需8.8度电!高管亲测小米汽车
豫北、豫西或发生崩塌、滑坡、泥石流 河南发布区域地质灾害黄色风险预警
惠城区教育局:将对南都曝光存在乱象的校外培训机构进行处罚
企退与事退抚恤金解析:生前养老金差距大,死后抚恤金不一样!
限时优惠!英特尔i5 12400F独显电脑到手价3599元
看过来!广西、广东、云南游客,免门票!
斯特林在切尔西,找到了快乐真谛,他完成了梅西一半的任务
财鑫闻丨A股市场持续调整 可转债抗跌 估值被推高 如何选择?
外媒:英国计划斥资1.3亿美元购买数千颗高性能人工智能芯片
国能晋江热电:多点借力夯实班组建设基石
吉林:新能源电源集群调控新模式正式运行
先健科技(01302.HK)Epione穿刺手术导航定位系统获正式注册批准
中央气象台8月21日10时继续发布暴雨蓝色预警
08月21日金纶高纤涤纶短纤为7700元
吉利睿蓝7预售:10万元起 单电机驱动
有个罕见反转出现
8月LPR不对称降息:1年期降10个基点 5年期以上不变
萍乡这些赶“烤”人,“炎”值爆表!
英雄联盟大发明家厉害吗 英雄联盟没有大发明家
今日申世京 run on(high kick3短腿的反击,申世京第几集出现了)
山东省社保待遇资格认证怎么认证?微信支付宝认证简单又方便!
小米恢复系统完整性
研究发现边缘冰区是大气汞重要来源
东方创业(600278)8月21日主力资金净卖出566.97万元
冠农股份(600251)8月21日主力资金净卖出485.29万元
铜峰电子(600237)8月21日主力资金净卖出1137.59万元
1-7月份山西省一般公共预算支出3361亿元
探岳黑火山版外观引关注:全黑磨砂质感
这是病!高铁一岁孩子哭闹,女子歇斯底里质问家长!
郭光灿院士:“量超融合”将成未来算力发展趋势
新车 | 售16.99万元起,长安览拓者探索版到店,竞争长城炮越野版
硅谷解禁自动驾驶出租车,Robotaxi不受限运营
定位纯电动跑车 名爵Cyberster国内亮相
华人健康:8月18日融资买入4427.3万元,融资融券余额6569.84万元
“药圣”李时珍的启示
自动驾驶汽车再曝事故 旧金山消防车被碰撞
山东费县一游客向景区工作人员泼热水?警方回应:泼水人行政拘留10天
什么?时尚名媛竟然还能“参与”造火箭!
新能源汽车L2辅助驾驶装车率已逼近40% 远高于燃油车
谨防二手车套路!男子付16800订金买二手凯迪拉克 结果却被骗
小米14 Ultra预计明年3月发布 IMEI数据库出现双版本
想买X5的等一等!新款国产X5即将发布 动力外观均有提升
奔驰GLE AMG版本上市:110.28-162.68万元