【算法模板】数学基础算法模版

2024-04-28 23:20
文章标签 算法 模版 模板 数学 基础

本文主要是介绍【算法模板】数学基础算法模版，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 数学基础
    • 试除法判定质数
    • 试除法分解质因数
    • 朴素筛法求素数
    • 线性筛法求素数
    • 试除法求所有约数
    • 约数个数和约数之和
    • 欧几里得算法
    • 求欧拉函数
    • 筛法求欧拉函数
    • 快速幂
    • 扩展欧几里得算法
    • 高斯消元解线性方程组
    • 递推法求组合数
    • 通过预处理逆元的方式求组合数
    • Lucas定理
    • 分解质因数法求组合数

数学基础

试除法判定质数

试除法是判断一个数是否为质数的常见方法。它的核心思想是，将该数从2开始，逐个尝试除以小于等于其平方根的整数。如果在这些尝试中有任何一个整数整除这个数，那么这个数就不是质数；否则，这个数就是质数。

算法思路：

  1. 如果数字小于2，直接返回False，因为质数从2开始。
  2. 从2开始，尝试除到小于等于该数平方根的每一个整数。
  3. 如果任何一个整数整除该数，则返回False，否则返回True。
bool is_prime(int x) {if (x < 2) return false;for (int i = 2; i <= x / i; i++)if (x % i == 0)return false;return true;
}

模板题 AcWing 866. 试除法判定质数

试除法分解质因数

试除法用于分解一个整数的质因数，并计算其质因数的次数。其思路是从2开始，逐个尝试整除，直到小于等于该数的平方根。

算法思路：

  1. 从2开始，尝试除到小于等于该数平方根的每一个整数。
  2. 如果该整数能够整除目标数，记录这个质因数以及它的出现次数，直到目标数不再可被整除。
  3. 如果经过所有检查后，目标数仍然大于1，那么该数也是质因数。
void divide(int x) {for (int i = 2; i <= x / i; i++)if (x % i == 0) {int s = 0;while (x % i == 0) x /= i, s++;cout << i << ' ' << s << endl;}if (x > 1) cout << x << ' ' << 1 << endl;cout << endl;
}

模板题 AcWing 867. 分解质因数

朴素筛法求素数

朴素筛法，又称埃拉托斯特尼筛法，适用于生成范围内所有素数的列表。其原理是从2开始，筛除每个素数的所有倍数。

算法思路：

  1. 创建一个布尔数组，用于标记数是否是素数，初始时全部设为True。
  2. 从2开始，如果该数没有被标记为非素数，则认为它是素数，并标记它的所有倍数为非素数。
  3. 重复以上步骤，直到到达范围上限。
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];             // st[x]存储x是否被筛掉void get_primes(int n) {for (int i = 2; i <= n; i++) {if (st[i]) continue;primes[cnt++] = i;for (int j = i + i; j <= n; j += i)st[j] = true;}
}

模板题 AcWing 868. 筛质数

线性筛法求素数

线性筛法是对朴素筛法的改进，确保每个合数只被其最小质因子筛选一次。其优点在于复杂度更低，每个合数只被筛选一次。

算法思路：

  1. 创建一个布尔数组，用于标记数是否是素数。
  2. 从2开始，如果该数没有被标记为非素数，则添加到素数列表中。
  3. 对于每个素数，如果当前数乘以素数不超过范围上限，则标记其为非素数。若当前数被素数整除，停止进一步标记。
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];             // st[x]存储x是否被筛掉void get_primes(int n) {for (int i = 2; i <= n; i++) {if (!st[i]) primes[cnt++] = i;for (int j = 0; primes[j] <= n / i; j++) {st[primes[j] * i] = true;if (i % primes[j] == 0) break;}}
}

模板题 AcWing 868. 筛质数

试除法求所有约数

试除法用于求一个整数的所有约数。其思路是从1开始，逐个尝试到该数的平方根，找出所有的约数。

算法思路：

  1. 从1开始，尝试到小于等于该数平方根的每一个整数。
  2. 如果该整数能够整除目标数，则记录这个整数和相应的商。
  3. 返回所有找到的约数，并按从小到大的顺序排序。
vector<int> get_divisors(int x) {vector<int> res;for (int i = 1; i <= x / i; i++)if (x % i == 0) {res.push_back(i);if (i != x / i) res.push_back(x / i);}sort(res.begin(), res.end());return res;
}

模板题 AcWing 869. 试除法求约数

约数个数和约数之和

这两个公式用于计算一个数的所有约数的个数和它们的总和。算法基于该数的质因数分解。

算法思路：

  1. 首先对数进行质因数分解，获得每个质因数和对应的次数。
  2. 约数个数的计算：每个质因子的次数加1，然后所有质因子次数的乘积。
  3. 约数之和的计算：对于每个质因子，求其从0到对应的次数的幂之和，然后将所有质因子幂之和相乘。
// 如果 N = p1^c1 * p2^c2 * ... * pk^ck
// 约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
// 约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

关于取模

(a + b) % p = (a%p + b%p) %p 
(a - b) % p = (a%p - b%p) %p 
(a * b) % p = (a%p * b%p) %p

这是一个关于正整数因数分解的公式。在公式中，N是一个正整数，表示为质因数分解形式：N = p1^c1 * p2^c2 * … * pk^ck，其中p1, p2, …, pk是N的所有质因数，c1, c2, …, ck分别是它们的对应指数。

根据你提供的公式：

  • N的约数个数可以通过公式 (c1 + 1) * (c2 + 1) * … * (ck + 1) 来计算，即将每个质因数的指数加1后相乘得到约数个数。
  • N的约数之和可以通过公式 (p1^0 + p1^1 + … + p1^c1) * … * (pk^0 + pk^1 + … + pk^ck) 来计算，即将每个质因数的幂次相加后相乘得到约数之和。

计算正整数N的约数个数

int numDivisors(int N) {int num = 1;for (int i = 2; i <= sqrt(N); i++) {int exp = 0;while (N % i == 0) {exp++;N /= i;}num *= (exp + 1);}if (N > 1) {num *= 2;}return num;
}

计算正整数N的约数之和

int sumOfDivisors(int N) {int sum = 1;for (int i = 2; i <= sqrt(N); i++) {if (N % i == 0) {int current_term = 1;int factor = 1;while (N % i == 0) {factor *= i;current_term += factor;N /= i;}sum *= current_term;}}if (N > 1) {sum *= (1 + N);}return sum;
}

模板题 AcWing 870. 约数个数, AcWing 871. 约数之和

欧几里得算法

欧几里得算法用于求解两个整数的最大公约数。它基于辗转相除的原则，即不断求解两个数的余数，直到余数为零。

算法思路:

  1. 给定两个整数a和b，如果b为零，则最大公约数是a。
  2. 否则，计算a除以b的余数，重新调用算法，用b和余数进行迭代。
  3. 直到余数为零，得到最大公约数。
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;
}

模板题 AcWing 872. 最大公约数

求欧拉函数

欧拉函数(\phi(x))用于计算小于等于x且与x互质的正整数的数量。计算欧拉函数通常需要质因数分解。

算法思路:

  1. 初始化结果为x。
  2. 从2开始，尝试整除目标数。如果能整除，则将结果乘以(1 - 1/p)。
  3. 对每个质因子，重复上述步骤，直到目标数被完全分解。
int phi(int x) {int res = x;for (int i = 2; i <= x / i; i++)if (x % i == 0) {res = res / i * (i - 1);while (x % i == 0) x /= i;}if (x > 1) res = res / x * (x - 1);return res;
}

模板题 AcWing 873. 欧拉函数

筛法求欧拉函数

筛法用于快速求解从1到某个范围内的所有欧拉函数。这种方法通过结合线性筛法来提高效率。

算法思路:

  1. 创建一个布尔数组，用于标记数是否是素数，并初始化一个数组存储欧拉函数值。
  2. 从2开始，如果该数没有被标记为非素数，则它是素数，并设置其欧拉函数值。
  3. 对于每个素数，计算其倍数的欧拉函数值，并根据质因子的关系调整欧拉函数值。
void get_eulers(int n) {euler[1] = 1;for (int i = 2; i <= n; i++) {if (!st[i]) {primes[cnt++] = i;euler[i] = i - 1;}for (int j = 0; primes[j] <= n / i; j++) {int t = primes[j] * i;st[t] = true;if (i % primes[j] == 0) {euler[t] = euler[i] * primes[j];break;}euler[t] = euler[i] * (primes[j] - 1);}}
}

模板题 AcWing 874. 筛法求欧拉函数

快速幂

快速幂算法用于快速计算(a^b \mod p)。其主要思想是通过二进制拆分幂次，以减少计算量。

算法思路:

  1. 初始化结果为1，并设置当前幂次。
  2. 根据k的二进制表示，对每一位进行判断。如果最低位为1，则将当前幂次乘到结果中。
  3. 将幂次平方，并右移二进制表示的最低位。
  4. 重复上述步骤，直到幂次完全被处理。
int qmi(int m, int k, int p) {int res = 1 % p, t = m;while (k) {if (k & 1) res = res * t % p;t = t * t % p;k >>= 1;}return res;
}

模板题 AcWing 875. 快速幂

扩展欧几里得算法

扩展欧几里得算法除了求解最大公约数，还能求得线性组合方程的整数解。其在求解一些数论和密码学问题时非常有用。

算法思路:

  1. 如果b为零，返回a作为最大公约数，同时设置x为1，y为0。
  2. 否则，递归调用算法，求解b和a % b的最大公约数，并交换x和y的顺序。
  3. 根据线性组合方程，调整x和y，以满足ax + by的关系。

int exgcd(int a, int b, int &x, int &y) {if (!b) {x = 1; y = 0;return a;}int d = exgcd(b, a % b, y, x);y -= (a / b) * x;return d;
}

模板题 AcWing 877. 扩展欧几里得算法

高斯消元解线性方程组

高斯消元算法用于求解线性方程组。它通过行列变换和消元来简化方程，最终获得解的形式。

算法思路:

  1. 通过行变换，将最大的系数移动到主对角线。
  2. 对于每个列，通过消元使得该列以下所有行的元素为零。
  3. 当完成所有列的操作后，若未完成所有行，则检测是否存在无解的情况。
  4. 对已消元的方程组，进行回代求解。
int gauss() {int c, r;for (c = 0, r = 0; c < n; c++) {int t = r;for (int i = r; i < n; i++)   // 找到绝对值最大的行if (fabs(a[i][c]) > fabs(a[t][c]))t = i;if (fabs(a[t][c]) < eps) continue;for (int i = c; i <= n; i++) swap(a[t][i], a[r][i]);      // 将绝对值最大的行换到最顶端for (int i = n; i >= c; i--) a[r][i] /= a[r][c];      // 将当前行的首位变成1for (int i = r + 1; i < n; i++)       // 用当前行将下面所有的列消成0if (fabs(a[i][c]) > eps)for (int j = n; j >= c; j--)a[i][j] -= a[r][j] * a[i][c];r++;}if (r < n) {for (int i = r; i < n; i++)if (fabs(a[i][n]) > eps)return 2; // 无解return 1; // 有无穷多组解}for (int i = n - 1; i >= 0; i--)for (int j = i + 1; j < n; j++)a[i][n] -= a[i][j] * a[j][n];return 0; // 有唯一解
}

模板题 AcWing 883. 高斯消元解线性方程组

递推法求组合数

递推法用于计算组合数。它利用递推关系，通过前序计算得出组合数的结果。

算法思路:

  1. 创建一个二维数组，存储组合数的计算结果。
  2. 通过递推关系，计算每一层的组合数。
  3. 遍历递推关系，填充组合数数组，直到计算出所有组合数。
for (int i = 0; i < N; i++)for (int j = 0; j <= i; j++)if (!j) c[i][j] = 1;else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;

模板题 AcWing 885. 求组合数 I

通过预处理逆元的方式求组合数

该方法使用快速幂计算逆元，以求出组合数的结果。它在模数情况下特别有用。

算法思路:

  1. 通过快速幂计算每个数的阶乘和阶乘的逆元。
  2. 使用组合数公式进行组合数的计算。
  3. 通过逆元的方式，避免直接除法操作。

int qmi(int a, int k, int p) {    // 快速幂模板int res = 1;while (k) {if (k & 1) res = (LL)res * a % p;a = (LL)a * a % p;k >>= 1;}return res;
}// 预处理阶乘的余数和阶乘逆元的余数
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i++) {fact[i] = (LL)fact[i - 1] * i % mod;infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}

模板题 AcWing 886. 求组合数 II

Lucas定理

Lucas定理用于求组合数，并可应用于大数情况下的组合数计算。

算法思路:

  1. 将组合数按模数分解为若干部分。
  2. 使用递归和分治法计算每一部分的组合数。
  3. 最终将所有部分的组合数乘积，获得组合数的结果。
int qmi(int a, int k, int p) {  // 快速幂模板int res = 1 % p;while (k) {if (k & 1) res = (LL)res * a % p;a = (LL)a * a % p;k >>= 1;}return res;
}int C(int a, int b, int p) {  // 通过定理求组合数C(a, b)if (a < b) return 0;LL x = 1, y = 1;  // x是分子，y是分母for (int i = a, j = 1; j <= b; i--, j++) {x = (LL)x * i % p;y = (LL)y * j % p;}return x * (LL)qmi(y, p - 2, p) % p;
}int lucas(LL a, LL b, int p) {if (a < p && b < p) return C(a, b, p);return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}

模板题 AcWing 887. 求组合数 III

分解质因数法求组合数

这种方法通过分解质因数的方式，求出组合数的真实值。

算法思路:

  1. 使用线性筛法，计算范围内的所有质数。
  2. 通过计算每个质因子的次数，求得组合数的质因数分解结果。
  3. 使用高精度乘法，将所有质因子按相应次数相乘，获得组合数的真实值。
当我们需要求出组合数的真实值，而非对某个数的余数时，分解质因数的方式比较好用：1. 筛法求出范围内的所有质数2. 通过 C(a, b) = a! / b! / (a - b)! 这个公式求出每个质因子的次数。 n! 中p的次数是 n / p + n / p^2 + n / p^3 + ...3. 用高精度乘法将所有质因子相乘int primes[N], cnt;     // 存储所有质数
int sum[N];     // 存储每个质数的次数
bool st[N];     // 存储每个数是否已被筛掉void get_primes(int n)      // 线性筛法求素数
{for (int i = 2; i <= n; i ++ ){if (!st[i]) primes[cnt ++ ] = i;for (int j = 0; primes[j] <= n / i; j ++ ){st[primes[j] * i] = true;if (i % primes[j] == 0) break;}}
}int get(int n, int p)       // 求n！中的次数
{int res = 0;while (n){res += n / p;n /= p;}return res;
}vector<int> mul(vector<int> a, int b)       // 高精度乘低精度模板
{vector<int> c;int t = 0;for (int i = 0; i < a.size(); i ++ ){t += a[i] * b;c.push_back(t % 10);t /= 10;}while (t){c.push_back(t % 10);t /= 10;}return c;
}get_primes(a);  // 预处理范围内的所有质数for (int i = 0; i < cnt; i ++ )     // 求每个质因数的次数
{int p = primes[i];sum[i] = get(a, p) - get(b, p) - get(a - b, p);
}vector<int> res;
res.push_back(1);for (int i = 0; i < cnt; i ++ )     // 用高精度乘法将所有质因子相乘for (int j = 0; j < sum[i]; j ++ )res = mul(res, primes[i]);

模板题 AcWing 888. 求组合数 IV

这篇关于【算法模板】数学基础算法模版的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/944535。

相关文章

算法day07

算法day07

第一题 30. 串联所有单词的子串         上题题意如下：          将w数组里面的字符串随机排列，只要在s字符串中找到相对应的w组成的字符串，则返回s中对应字符串首位元素的第一个下标；                  有上述题意所知，解题思路如上一题故事，本题采用hash表和滑动窗口的模型；         首先对于words字符串数组进行处理：
阅读更多...
【算法】网络图中的dfs

【算法】网络图中的dfs

快乐的流畅：个人主页 个人专栏：《算法神殿》《数据结构世界》《进击的C++》 远方有一堆篝火，在为久候之人燃烧！ 文章目录 引言一、单词搜索二、黄金矿工三、不同路径 |||四、图像渲染五、岛屿数量六、岛屿的最大面积七、被围绕的区域八、太平洋大西洋水流问题九、扫雷游戏总结 引言 在二维网络图中的dfs，反而一般不需要画决策树，因
阅读更多...
算法工程师面试问题 | YOLOv8面试考点原理全解析（一）

算法工程师面试问题 | YOLOv8面试考点原理全解析（一）

本文给大家带来的百面算法工程师是深度学习目标检测YOLOv8面试总结，文章内总结了常见的提问问题，旨在为广大学子模拟出更贴合实际的面试问答场景。在这篇文章中，我们还将介绍一些常见的深度学习目标检测面试问题，并提供参考的回答及其理论基础，以帮助求职者更好地准备面试。通过对这些问题的理解和回答，求职者可以展现出自己的深度学习目标检测领域的专业知识、解决问题的能力以及对实际应用场景的理解。同时，这也是为
阅读更多...
Vue原理学习:vdom 和 diff算法(基于snabbdom)

Vue原理学习:vdom 和 diff算法(基于snabbdom)

vdom 和 diff 背景 基于组件化，数据驱动视图。只需关心数据，无需关系 DOM ，好事儿。 但是，JS 运行非常快，DOM 操作却非常慢，如何让“数据驱动视图”能快速响应？ 引入 vdom 用 vnode 表示真实 DOM 结构  <div id="div1" class="container"><p>vdom</p><ul style="font-size: 20px">
阅读更多...
代码随想录算法训练营第五十五天| 583. 两个字符串的删除操作 ，72. 编辑距离

代码随想录算法训练营第五十五天| 583. 两个字符串的删除操作 ，72. 编辑距离

目录 题目链接： 583. 两个字符串的删除操作 思路 代码 题目链接： 72. 编辑距离 思路 代码 总结 题目链接：583. 两个字符串的删除操作 思路         ①dp数组，dp[i][j]表示下标以i-1结尾的word1和下标以j-1结尾的word2若要相等，所需删除元素的最小次数         ②递归公式，当word1[i-1] == word2
阅读更多...
LeetCode算法题：15. 三数之和（Java）

LeetCode算法题：15. 三数之和（Java）

题目描述 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请 你返回所有和为 0 且不重复的三元组。 注意： 答案中不可以包含重复的三元组。 示例 1： 输入：nums = [-1,0,1,2,-1
阅读更多...
数学期望：小红拿宝箱

数学期望：小红拿宝箱

https://ac.nowcoder.com/acm/contest/80259/F 我们先从1--n每一个元素看，对于a[i]，可以后悔，这样相当于在n个元素中挑2个的期望， 为2*sum/n，假如没有后悔，剩下的期望就是(sum-a[i])/(n-1)了，此时我们还有一次反悔机会 我们不妨先排个序，假如我们选到了比期望大的数那么我们就直接选（否则下一次就是期望了），反之我们就返回使其值
阅读更多...
算法：解码方法（动态规划）—— decode-ways(Dynamic programming)

算法：解码方法（动态规划）—— decode-ways(Dynamic programming)

problem： A string “s” is consisted of number characters. If thesubstring value of one or two adjacent characters in “s” is between 1 and 26,the substring can be converted to an alphabet. The rule i
阅读更多...
持续总结中！2024年面试必问 100 道 Java基础面试题（五十）

持续总结中！2024年面试必问 100 道 Java基础面试题（五十）

上一篇地址：持续总结中！2024年面试必问 100 道 Java基础面试题（四十九）-CSDN博客 九十九、请解释Java中的单例模式及其实现方式 单例模式（Singleton Pattern）是一种常用的软件设计模式，它确保一个类只有一个实例，并提供一个全局访问点来获取这个实例。单例模式在Java中的实现有多种方式，每种方式都有其特点和适用场景。 单例模式的特点： 单例类只能有一个实例：
阅读更多...
基础Socket通信

基础Socket通信

本文使用三个类完成客户端与服务端的 Socket 通信。     Client：客户端，可完成信息收发     Server：服务端，监听客户端请求，为了方便，也可以收发信息     MessageHandleRunnable：实际收发信息的 Runnable 类      import java.io.IOException;import java.net.ServerSoc
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2