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

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。

相关文章

C++ 数据结构算法 学习笔记(25) - 图及其企业级应用

C++ 数据结构算法 学习笔记(25) - 图及其企业级应用

C++ 数据结构算法 学习笔记(25) - 图及其企业级应用 图的故事导入 故事情节 Jack 自从买车后，交通出行方便了，心自然就野了！身边的各种朋友自然就多了起来！ 有一天晚上，一个年轻漂亮的女同事生日，Jack 受邀请准时爽约！Jack 亲睐此女已久，只是 介于家里的 LD 不敢越雷池一步，但是，一有机会，Jack 都会和此女接近，经常在一起，所以可 以说是就当个哥们吧！ Jack 当
阅读更多...
【算法】dfs

【算法】dfs

快乐的流畅：个人主页 个人专栏：《算法神殿》《数据结构世界》《进击的C++》 远方有一堆篝火，在为久候之人燃烧！ 文章目录 引言一、全排列1. 决策树2. 设计代码1. 全局变量2. dfs函数3. 细节问题 二、子集解法一1. 决策树2. 设计代码1. 全局变量2. dfs函数3. 细节问题 解法二1. 决策树2. 设计代码1. 全局
阅读更多...
使用script标签来做html页面的模板

使用script标签来做html页面的模板

html页面经常需要js动态加载html内容，一般都采取js拼接html 的方式实现，最近发现可以使用<script>标签来做个html模板，这样更方便。并且代码可读性也增强了。 <!DOCTYPE html><html><head><meta name="viewport" content="width=device-width, initial-scale=1,maximum-scale=
阅读更多...
二、计算机基础(Java零基础二)

二、计算机基础(Java零基础二)

🌻🌻目录 一、认识计算机二、计算机的组成2.1 计算机硬件（摸得着，看得见）2.1.1 计算机硬件组成2.1.2 冯.诺依曼(计算机之父)体系结构 2.2 计算机软件（摸不着，看不见） 三、电脑常用快捷键四、CMD打开方式和DOS命令4.1 打开CMD的方式4.2 常用的DOS命令 一、认识计算机 什么是计算机 Computer:全称电子计算机，俗称电脑；能够按照程序运
阅读更多...
C语言基础-枚举类型

C语言基础-枚举类型

C语言中的枚举类型（enum）是一种用户定义的数据类型，它允许为整数常量指定一个名称，使得代码更易于阅读和维护。枚举类型本质上是一种特殊的整数类型，但每个枚举值都有一个名字，而不是直接使用整数。 枚举类型的定义 枚举类型通过enum关键字来定义，下面是一个简单的例子： enum Days { Sunday, Monday, Tuesday, Wednesday, Thursday,
阅读更多...
＜MySQL＞ 数据库基础

＜MySQL＞ 数据库基础

目录 一、数据库概念          （一）什么是数据库 （二）数据库存储介质 （三）常见数据库 二、数据库基本操作 （一）连接数据库 （二）使用数据库 （三）服务器、数据库、表关系 三、MySQL语句分类 四、MySQL架构 五、存储引擎 （一）查看存储引擎 （二）存储引擎间的区别 一、数据库概念 （一）什么是数据库 数据库是按照数据结构来组织、存储和管理
阅读更多...
第二课，python基础语法（一），认识字面量和变量、注释

第二课，python基础语法（一），认识字面量和变量、注释

一，字面量 （一）什么是字面量 被写下来的的固定的值，称之为字面量 （二）常见的三种字面量类型 （三）练习一下，使用print去输出三种不同类型的字面量：10，3.14，”hello”  二，注释 初学编程时，常常会有一种感觉，感觉有时候都不知道自己写的是啥，要干啥？ （一）注释的作用 在程序代码中对程序代码进行解释说明的文字，计算机不看注释，注释是给我们程
阅读更多...
重拾数据结构与算法(七)查找算法

重拾数据结构与算法(七)查找算法

java知识归纳总结 github: https://a870439570.github.io/interview-docs 顺序表查找 顺序查找又叫线性查找，是最基本的查找技术。它的查找过程是:从表中第一个(或最后一个)记录开始，逐个进行记亲的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录;如果直到最后一个(或第一个)记录，其关键字和给定值比较都不等时，则表中
阅读更多...
目标检测YOLO实战应用案例100讲-基于深度学习的交通场景多尺度目标检测算法研究与应用（下）

目标检测YOLO实战应用案例100讲-基于深度学习的交通场景多尺度目标检测算法研究与应用（下）

目录  3.2 基于空洞卷积的特征融合模块设计  3.3 改进k-means聚类算法的anchor尺寸优化设计
阅读更多...
函数模板底层本质

函数模板底层本质

#include<iostream>using namespace std;template<typename T1>T1 ave(T1 a, T1 b) { return a + b;}int main() {ave(100, 200);ave(short(100), short(200));return 0;} 反汇编代码 模板本质是编译器帮忙生成了不同的函数 就算
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2