最新要闻
- 最新快讯!40万级乱杀!全新国产奔驰GLC配置曝光:四款车型、两种外观
- 全球焦点!Gamerant赞《黑神话·悟空》:虚幻5打造《西游记》传说值得期待
- 天天要闻:这外观似曾相识!荣耀Magic 5 Lite曝光:后置圆环三摄
- 全球快看:《狂飙》爆火出圈!《孙子兵法》登顶淘宝热搜 发货要等25天
- 男子2月没摘隐形眼镜:镜片长到眼球上
- 每日信息:对标三星索尼!SK海力士重组CMOS图像传感器团队
- 天天微头条丨网友吐槽美国医院3小时拔不出一根鱼刺 急诊那是真不急
- 全球微资讯!耶路撒冷老城千年护城河道惊现神秘手印 专家:或为工人恶作剧
- 最新快讯!立减40元:露得清氨基酸洗面奶19.9元到手 男女通用
- 世界看热讯:5G四足机器人“入职”中国电信核心机房:支持自主巡航 360度旋转夜视
- 猛禽之王!摄影爱好者抓拍到金雕展翅抓羊场面:超震撼
- 全球今亮点!《狂飙》爆火后 《孙子兵法》解析成微信读书飙升榜第一名
- 天际汽车刹车失灵 故障不断!车主售后找不到人
- 当前资讯!雷蛇宣布2月2日发布新品:或为毒蝰系列新品
- 72G《英雄联盟》源代码被盗 拳头游戏拒绝打钱 黑客:100万美元起拍
- 多地现宰客乱象 央视评宰客事件:“一锤子买卖”?
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
当前速讯:1.29数论课笔记
o.O
一、\(O(\sqrt{n})\) 判断质数
枚举 \(\left[2,\sqrt{n}\right]\) 中的数,判断是否能整除 \(n\) ,如果都没有则返回 \(true\)。
为什么不用枚举 \(\sqrt{n}\) 以上的数:假设有一个数 \(a\in\left[\sqrt{n},n\right]\) 是 \(n\) 的约数,那么显然 \(\lfloor \dfrac{n}{a} \rfloor\) 也是 \(n\) 的约数,而 \(\lfloor \dfrac{n}{a} \rfloor\) 必然是小于 \(\sqrt{n}\) 的,在之前就已经被检查过了。
点击查看代码
bool isprime(int x){for(int i=2;i*i<=x;i++){if(x%i)return false;}return true;}
二、质因数分解
用一个 \(vector\) 存储质因数,遍历 \(\left[2,n\right]\) 中的所有数,检查是否是 \(n\) 的约数,如果是则反复除至 \(n\) 的因子不含有当前枚举的数。
(相关资料图)
为什么遍历的是所有的数,筛出来的却都是质数因数:假设 \(n\) 有一个合数约数 \(x\),那么 \(x\) 本身还可以写成若干个小于 \(x\) 的质数相乘,而这些小于 \(x\) 的数已经在之前筛过了。
点击查看代码
vector p;void work(int x){for(int i=2;i<=x;i++){while(x%i==0){p.emplace_back(i);x/=i;}}}
三、算术基本定理
对于所有的大于1的整数 \(a\) 都有:
\[a=\sum_{i=1}^{k}p_i^{c_i},p\in Prime\]事实上就是分解质因数,把 \(a\) 分解成 \(k\) 个质数的若干次幂之和。代码基本同分解质因数。
点击查看代码
vector p,c;void work(int x){for(int i=2;i<=x;i++){int cnt=0;while(x%i==0){if(!cnt)p.emplace_back(i);x/=i,cnt++;}if(cnt)c.emplace_back(cnt);}}//k=p.size()或c.size()
四、埃氏筛质数
筛除每个质数的倍数,剩下的即为质数。
五、欧拉筛质数
欧拉筛相对埃氏筛的进步就是最大限度地减少了重复筛出合数的情况。
1.外层枚举一个数 \(i\)
for(int i=2;i<=n;i++){
2.如果在这之前 \(i\) 没有被标记为合数(即 \(c_i=1\)),就将 \(i\) 加入质数集合
if(!c[i])p.emplace_back(i);
3.然后枚举所有的已知质数,作为一个“基底”\(base\)。
for(int base:p){
4.先来检查 \(base\) 的 \(i\) 倍是否已经超出了 \(n\),如果是直接跳出内层枚举
if(i*base>n)break;
5.将 \(base\) 的 \(i\) 倍标记为合数
c[base*i]=1;
6.如果 \(i\) 是 \(base\) 的倍数,跳出内层枚举防止重复筛除
if(i%base==0)break;
当 \(i\) 是 \(base\) 的倍数时就跳出内层,为什么能防止重复:还是记内层枚举到的质数为 \(base\)。首先要理解到 \(i\) 的含义在枚举内层时发生了转变。——在外层时,\(i\) 的含义就是要被检查是否为质数的一个数——在内层时,\(i\) 成为了“倍数”,表示现在要标记 \(base\) 的 \(i\) 倍为合数注意到并不是筛除 \(i\) 的 \(base\) 倍,而是筛除 \(base\) 的 \(i\) 倍!然后来讨论为什么 \(i\) 是 \(base\) 的倍数后面就会重复。我们设 \(i=a*base\),其中 \(a\) 是不为 \(1\) 的整数。假设我们当前已经满足
i%base==0
,但不跳出,就会枚举到下一个质数,记其为 \(base"\)。这样我们就会尝试标记 \(base"\) 的 \(i\) 倍为合数。虽然它确实是合数,但它也能被 \(base\) 的其他倍筛去,这就导致了重复。具体地,我们设当前试图筛去的数为 \(k\),即 \(k=base"*i\)。由于之前有 \(i=a*base\),所以 \(k\) 也能写成 \(k=base*(a*base")\)这也就意味着,目前的 \(k\) 也会在外层 \(i\) 枚举到 \(a*base"\)、内层再次枚举到 \(base\) 时作为“\(base\) 的 \(a*base"\) 倍”被筛去举个例子,如果 \(i=4,base=2\),按理说就应该跳出,若不跳出枚举到下一个 \(base"=3\),试图筛去的 \(k=base"*i=3*4=12=2*6=base*6\)
如何保证在 \(i\) 枚举到 \(a*base"\) 时,内层循环不会在再次枚举到 \(base\) 之前跳出:注意到 \(i=a*base\) 中,\(a\) 的最小因子一定是不小于 \(base\) 的。如果 \(a\) 有小于 \(base\) 的因子,那么内层循环一定会在枚举到 \(base\) 之前就跳出又因为 \(base"\) 显然大于 \(base\)所以 \(a*base"\) 的最小因子也是大于 \(base\) 的,这就意味着当 \(i\) 枚举到 \(a*base"\)时,其内层循环在枚举到 \(base\) 之前不会存在满足
i%base==0
这个语句的情况,因为那当且仅当 \(a*base"\) 有小于 \(base\) 的因数时才有可能发生。
欧拉筛整体代码
点击查看代码
bool c[MAXN];vector p;void work(int n){for(int i=2;i<=n;i++){if(!c[i])p.emplace_back(i);for(int base:p){if(i*base>n)break;c[base*i]=1;if(i%base==0)break;}}}
七、gcd,lcm,exgcd
gcd与exgcd的具体证明在之前的文章。这里给出 \(\gcd(a,b)*\operatorname{lcm}(a,b)=a*b\) 的证明。
先考虑证明互质的两数 \(p,q\) 的最小公倍数为 \(p*q\)由于显然 \(p*q\) 是 \(p,q\) 的公倍数,设其不是最小公倍数则存在一个整数 \(k\),使得 \(\dfrac{p*q}{k}\) 仍为整数且是 \(p\) 和 \(q\) 的倍数因为是 \(p\) 的倍数,则 \(\dfrac{\dfrac{p*q}{k}}{p}=\dfrac{p*q}{p*k}=\dfrac{q}{k}\) 为整数因为是 \(q\) 的倍数,则 \(\dfrac{\dfrac{p*q}{k}}{q}=\dfrac{p*q}{q*k}=\dfrac{p}{k}\) 为整数这意味着 \(\gcd(p,q)=k\) 因为 \(p=\dfrac{p}{k}*k,q=\dfrac{q}{k}*k\) 而 \(\dfrac{p}{k},\dfrac{q}{k}\) 均为整数,与 \(p,q\) 互质矛盾,故互质的两数 \(p,q\) 的最小公倍数为 \(p*q\)
再证明 \(\gcd(a,b)*\operatorname{lcm}(a,b)=a*b\)记 \(\gcd(a,b)=g\),则\(a=a"g,b=b"g\)显然此处 \(\gcd(a",b")=1\),否则 \(\gcd(a,b)\) 应为 \(g*\gcd(a"*b")\)于是我们知道 \(\operatorname{lcm}(a",b")=a"*b"\)又注意到 \(\operatorname{lcm}\) 满足结合律,即 \(\operatorname{lcm}(ac,bc)=\operatorname{lcm}(a,b)*c\),证明显然又因为 \(\operatorname{lcm}(a,b)=\operatorname{lcm}(a,b)\)所以 \(\operatorname{lcm}(a,b)=\operatorname{lcm}(a"g,b"g)=\operatorname{lcm}(a",b")*g=a"*b"*g\)两边同乘 \(g\) 得 \(g*\operatorname{lcm}(a,b)=a"*g*b"*g\)由一开始的三个定义 \(\gcd(a,b)=g,a=a"g,b=b"g\) 替换得\(\gcd(a,b)*\operatorname{lcm}(a,b)=a*b\)
给出三个算法的代码
点击查看代码
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}int lcm(int a,int b){return a*b/gcd(a,b);}void exgcd(int a,int b,int &x,int &y){if(b==0){x=1,y=0;}else{exgcd(b,a%b,y,x);y-=(a/b)*x;}}
TBC
当前速讯:1.29数论课笔记
最新快讯!40万级乱杀!全新国产奔驰GLC配置曝光:四款车型、两种外观
全球焦点!Gamerant赞《黑神话·悟空》:虚幻5打造《西游记》传说值得期待
天天要闻:这外观似曾相识!荣耀Magic 5 Lite曝光:后置圆环三摄
全球快看:《狂飙》爆火出圈!《孙子兵法》登顶淘宝热搜 发货要等25天
男子2月没摘隐形眼镜:镜片长到眼球上
焦点日报:时区介绍
前沿热点:Matlab导入多个.mat文件进行画图
每日信息:对标三星索尼!SK海力士重组CMOS图像传感器团队
天天微头条丨网友吐槽美国医院3小时拔不出一根鱼刺 急诊那是真不急
全球微资讯!耶路撒冷老城千年护城河道惊现神秘手印 专家:或为工人恶作剧
最新快讯!立减40元:露得清氨基酸洗面奶19.9元到手 男女通用
世界看热讯:5G四足机器人“入职”中国电信核心机房:支持自主巡航 360度旋转夜视
乘法逆元
今日看点:C++11简易线程池实现
002-dockerfile部署java项目
当前观点:springboot~openfeign开启熔断之后MDC为null的理解
焦点播报:WebAPI_DAY1
猛禽之王!摄影爱好者抓拍到金雕展翅抓羊场面:超震撼
全球今亮点!《狂飙》爆火后 《孙子兵法》解析成微信读书飙升榜第一名
天际汽车刹车失灵 故障不断!车主售后找不到人
当前资讯!雷蛇宣布2月2日发布新品:或为毒蝰系列新品
72G《英雄联盟》源代码被盗 拳头游戏拒绝打钱 黑客:100万美元起拍
焦点要闻:关于pacemaker中资源启动的位置条件约束Location Constraints
【天天快播报】Codeforces Round #847 (Div. 3) ABCDE
焦点滚动:win32com操作word API精讲 第八集 Range和Selection的区别
多地现宰客乱象 央视评宰客事件:“一锤子买卖”?
【世界新要闻】明年的苹果iPad Pro将是重头戏!屏幕、后盖全都升级了
50只独立包装 超亚儿童N95医用防护口罩47.9元
全球热文:比亚迪:研发团队目前已覆盖各个电池技术路线
精选!无岳不成村!山东有个公交站叫“满江红” :住着岳飞后代
视焦点讯!《云管理服务白皮书》总结
【网关开发】7.Openresty使用cosocket API 发送http与tcp网络请求
美语发音【总结】
以前票房反超了会画海报恭喜对方:《满江红》却冷嘲热讽
全球今热点:碾压对手!OPPO Find X6工程机亮相:标准版都有潜望长焦
谷歌裁员细节曝光:开源主管被裁 61岁程序员在线求职
10分拉满!IGN发布《流浪地球2》影评:超越国际一流水准
环球新动态:全网音乐免费下载,音乐下载工具,音乐免费下载mp3格式,音乐下载器,小说下载,小说阅读,磁力链接聚合搜索,每日美女壁纸,如何免费下载想听的音乐或小说
天天日报丨【算法训练营day29】LeetCode491. 递增子序列 LeetCode46. 全排列 LeetCode47. 全排列II
关于前端低代码的一些看法
奔驰车主扔钱加油大姐捡钱偷抹泪引热议 当事人回应:网友愤怒素质差到家
动态焦点:蹭热度有风险 电商老店使用流浪地球标识遭索赔15万
当前速讯:海外观众热评《流浪地球2》:中国科幻片惊艳 比全球票房第四《阿凡达2》好看
要买的抓紧了!宝马将于2月起涨价:最高2万元
世界观天下!21岁男子撞车后向27岁“叔叔”道歉 车主果断索赔
【报资讯】骁龙778G还能再战!荣耀50/60系列获MagicOS 7.0升级
每日消息!博主赞特斯拉研发支出巨大:比亚迪、奔驰、理想都比不过
5支39.9元超划算:高露洁牙膏多效护理实惠家庭装套大促
Python工具箱系列(二十三)
天天观速讯丨JavaScript 条件判断与比较运算
环球热推荐:Python 的垃圾回收机制【译】
世界观焦点:Java 如何高亮 Excel 中低于或高于平均值的单元格
每日时讯!一加11同款!一加Ace 2外观首曝:环形镜头设计
全球资讯:春节假期后全国大部地区气温回升:南方最高可达20度 暖如春分
全球播报:生日蛋糕网店使用“流浪地球”标识 遭中影索赔15万
不是云南也不是海南!四川春节游客接待量全国第一
全球观焦点:吉利真会玩儿:汽车挡风玻璃上实现烟花秀
sacai是什么牌子?sacai有中国官网吗?
孑孓的读音是什么?孑孓是什么意思?
手机水货是什么意思?手机水货和行货有什么区别?
木棉花的春天大结局是什么?木棉花的春天全部演员表
绿芜是谁演的?绿芜为什么投河自尽?
电脑出现报警声是怎么回事?电脑出现报警声怎么解决?
松下电饭煲质量怎么样?松下电饭煲怎么调时间?
【环球聚看点】指向立体星(随便起的名)的建立与使用
小米2a手机是什么系统?小米2A手机充电保护怎么打开?
诺基亚210什么时候上市的?诺基亚210手机参数
戴尔的台式机怎么进入bios?戴尔台式机开不了机怎么办?
跑2500公里高速 踩着最后几秒过收费站:女子直呼惊险刺激
今日最新!流浪地球2原来是在青岛流浪 流亭机场戏份最多
全球观察:1:1真机开模!绿联iPhone钢化膜新年大促:2片到手5.22元起
外卖小哥过年3天赚2695元:年三十到初二上班不回家
环球关注:新一代宝马X1或将3月上市:尺寸再加长、堪比大哥X3
flash8.ocx或其附件之一不能正确注册
【全球速看料】Linux下docker安装部署
当前通讯!芬兰一动物园拟送大熊猫回中国:缺钱养不了
环球今头条!微软逼你升级Win11?Windows 10 ISO等正常下载
门店329元 361° 云翎运动鞋89元到手:2.7折
当前最新:中国科学家打造“类真人皮肤”:受伤1小时完全愈合
全球通讯!特斯拉强推“单踏板”遭吐槽 博主直言:价值观、是非观畸形
环球热门:读Java8函数式编程笔记04_类库
精彩看点:PHP反序列化新手入门学习总结
k8s~fluentd从kafka到elk
天天日报丨《满江红》官方连续发文回应争议扩散:统编教材删除岳飞满江红?从未选编
【天天新要闻】国内还有人看吗?漫威超英大片《黑豹2》被偷跑:1080p高清版流出
【世界快播报】卖价6.5亿 全球订单超1035架:国产大飞机C919有望3月载客飞行
今热点:评分不断下跌 电影《满江红》起诉4位微博大V 复旦教授回应
票房超24亿 中国科幻片里程碑!郭帆回应《流浪地球3》:放心了 喜欢接着拍
世界信息:博客主题 Lite
《满江红》票房超29亿!游客排长队打秦桧雕像:大妈亮出鞋底猛抽
无人机革命!麻省理工学院开发出超低噪音螺旋桨
【全球时快讯】node借助jsonwebtoken生成token以及验证token是否过期
真着急!中国显卡厂商首次曝光RTX 4060、RTX 4050
当前动态:有航司开33万高薪急招空乘:送八险二金、1.5年单身公寓
天天新资讯:《熊出没》系列电影累计票房超50亿!观众看《深海》突遇屋顶漏水
当前资讯!MySQL笔记01: MySQL入门_1.3 MySQL启动停止与登录
环球即时:手把手教你搭建mongodb分片集群
女子投简历被告知不招豫籍 直呼地域歧视很不公平:网友力挺河南人
全球看点:神了!锐龙9 7900X反而比锐龙9 7900便宜 还送32GB内存