[编程笔记]-Knapsack_Problem(Basic)背包问题（基础版）

[编程笔记]-Knapsack_Problem(Basic)背包问题（基础版）

概览背包问题，就是给定你一些背包和一些物品，通常情况下给出物品的价值和体积，再在不同类型中给定不同的限制条件，最后往往希望你给出能获得的最大价值。 01背包要求限制背包的最大体积，给出每种物品的体积和价值，每种物品只有一个，求能获得的最大价值。 解决基础版考虑状态dp[i][j]，表示在前i件物品中有j的体积可以获得的最大利润。 对于每个dp[i][j]，有两种情况：选不选第j件物品。 若选，则
编程笔记 > 动态规划
#原创 #编程 #c++ #笔记 #倍增 #动态规划 #背包问题
[编程笔记]-Chinese_Remainder_Theorem中国剩余定理

[编程笔记]-Chinese_Remainder_Theorem中国剩余定理

前言刚打完cf，当前时间1:04。 链接就不放了，照着标签去找吧，总能找到的。 解决方案一互质若m1, m2, m3, …, mk两两互质 满足如下条件： x≡a1(mod m1)x≡a2(mod m2)x≡a3(mod m3)…x≡ak(mod mk) 设M=m1m2m3…mk Mi=M/mi，就是除了mi外所有m的乘积。 因为所有m两两互质，所以Mi与mi互质
编程笔记 > 数学知识
#原创 #编程 #c++ #笔记 #数学 #乘法逆元 #拓展欧几里得算法 #质数 #中国剩余定理
[编程笔记]-Linear_Congruence_Equation线性同余方程

[编程笔记]-Linear_Congruence_Equation线性同余方程

概念形如ax≡b(mod m)的方程 前置[编程笔记]-Bezout’s_Lemma裴蜀定理（乘法逆元页面尚未创建，可以去快速幂看看概念）[编程笔记]-Extended_Euclidean_Algorithm拓展欧几里得算法 求解乘法逆元暂时没时间写，等把乘法逆元搞出来再写吧。 拓展欧几里得算法线性同余方程等价于ax=my+b(y∈Z)ax-my=b 设y’=-y a
编程笔记 > 数学知识
#原创 #编程 #c++ #笔记 #数学 #乘法逆元 #裴蜀定理 #拓展欧几里得算法 #线性同余方程
[编程笔记]-Extended_Euclidean_Algorithm拓展欧几里得算法

[编程笔记]-Extended_Euclidean_Algorithm拓展欧几里得算法

前置在学习拓展欧几里得算法前，建议先阅读裴蜀定理和乘法逆元两个页面了解本算法的作用。[编程笔记]-Bezout’s_Lemma裴蜀定理（乘法逆元页面尚未创建，可以去快速幂看看概念） 另外，如果你不知道欧几里得算法（辗转相除法），建议去约数基础部分先学习一下。[编程笔记]-Divisor_Basis约数基础 实现首先，既然是拓展欧几里得算法，肯定要从欧几里得算法拓展。 这里直接给出（证明见欧几里得算
编程笔记 > 数学知识
#原创 #编程 #c++ #笔记 #数学 #乘法逆元 #裴蜀定理 #最大公约数 #拓展欧几里得算法 #欧几里得算法
[编程笔记]-Bezout's_Lemma裴蜀定理

[编程笔记]-Bezout's_Lemma裴蜀定理

定理gcd(a,b)|ax+bya、b都是是gcd(a,b)的倍数，对于任意不全为零整数x、y所以gcd(a,b)|ax+by 因此a、b能凑出来的最小的数就是它的最大公约数。 ax+by=gcd(a, b)对于任意正整数a, b，一定存在非零整数x, y，使得ax+by=gcd(a, b) 证明：我们可以使用构造法 构造出一种方式，对于任意正整数a, b，一定存在非零整数x,
编程笔记 > 数学知识
#原创 #编程 #c++ #笔记 #数学 #裴蜀定理 #最大公约数 #拓展欧几里得算法
[编程笔记]-Binary_Exponentiation快速幂

[编程笔记]-Binary_Exponentiation快速幂

思想把a的k次方分解成a的（2的次方）次方之积。 也就是把k分成2的不同次方相加嘛。容易得到，2的每个次方最多只会出现一次（不然就能进位算进更高一次的次方里面去了）。 差不多就是这样。 时间复杂度O(logk)（k为幂数） 实现递归法很简单，根据思想就能得出。每次都把次方平均分，如果是奇数，就在结果处额外乘一个n即可，然后递归次方的二分之一，直到0次方。 迭代法事实上，可以把次数写出二进制写法，然
编程笔记 > 数学知识
#原创 #编程 #c++ #笔记 #数学 #倍增 #快速幂 #乘法逆元
[编程笔记]-Fermat's_Little_Theorem费马小定理
[编程笔记]-Euler's_Totient_Function欧拉函数

[编程笔记]-Euler's_Totient_Function欧拉函数

概念φ(n)表示1~n之中与n互质的数的个数 令N=P1α1*P2α2*P3α3*…*Pkαk 则φ(N)=N(1-1/P1)(1-1/P2)(1-1/P3)…(1-1/Pk) 推导 求出N的质因数 从1~N中去掉P1，P2到Pk的倍数。 加上所有Pi*Pj的倍数，因为第二步把它们多减了一次。 减去所有Pi*Pj*Pk的倍数，因为第三步把
编程笔记 > 数学知识
#原创 #编程 #c++ #笔记 #数学 #质数 #欧拉函数 #线性筛 #欧拉定理 #费马小定理
[编程笔记]-Divisor_Basis约数基础
[编程笔记]-Prime_Basis质数基础