Java教程

dls数论课程学习

本文主要是介绍dls数论课程学习，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

数论

整除/gcd

一些常见的结论

1-n之间的素数个数：n/lnn 级别的
第n个素数的大小：nlogn级别大小
1-n的倒数和：logn级别
1-n之间素数的倒数和：loglogn级别的

a|c, b|c, (a, b) = 1 --> ab|c,  a,b分别是c的一些质因子乘积，且a,b没有相同的质因子，所以c%(ab)==0
                                或者：[a, b]|c. 其中[a,b] = ab|(a, b) = ab
a|bc, (a,b) = 1  ---> a|c 
p|ab ---> p|a或p|b

所有公倍数都是最小公倍数的倍数
所有公约数都是最大公约数的约数

欧几里得

// 时间复杂度：log(min(a, b))
// (a, b) = (b, a mod b) 分类讨论可以发现每做一次都有一个数减小至少一半
// n个数依次做欧几里得，时间复杂度是n+log(max(ai))，不是nlogn,因为有个全局的最小公约数
// 最小公倍数推荐写法:(a/gcd(a, b))*b

// 另一种求公约数的方法
// 主要用于高精度取余
// int128等也比较快

裴蜀定理

// a, b, (a, b)|d  <--> au+bv=d 存在整数解
// 构造证明

同余

筛法

这篇关于dls数论课程学习的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航