数学知识--(欧拉函数,快速幂,扩展欧几里得算法)

2024-04-06 13:44

本文主要是介绍数学知识--(欧拉函数,快速幂,扩展欧几里得算法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文用于记录个人算法竞赛学习,仅供参考

目录

一.欧拉函数

 二.欧拉函数模板

三.用筛法求每个数的欧拉函数

 四.快速幂

 五.扩展欧几里得算法

 六.用扩展欧几里得算法求线性同余方程


一.欧拉函数

 即有一个数n, n通过质因数分解得到n=^{​{_{\rho 1}}^{\alpha 1} \cdot {_{\rho 2}}^{\alpha 2} ... {_{\rho k}}^{\alpha k}}

通过欧拉函数有\phi (n) = n(1-\frac{1}{\rho 1})(1-\frac{1}{\rho 2})...(1-\frac{1}{\rho k})

证明:容斥原理

 二.欧拉函数模板

\phi (n) = n(1-\frac{1}{\rho 1})(1-\frac{1}{\rho 2})...(1-\frac{1}{\rho k})

实际上就是分解质因数

时间复杂度:O(n^{\frac{1}{2}})

//计算一个数的欧拉函数的值
int phi(int x)
{int result = x;//分解质因数for (int i = 2; i <= x / i; i++){if (x % i == 0){//注意变形result = result / i * (i - 1);//将质数i除干净while (x % i == 0)x /= i;}}if (x > 1)result = result / x * (x - 1);return result;
}

三.用筛法求每个数的欧拉函数

求一个数的欧拉函数是O(n^{\frac{1}{2}}), 用遍历每个数的方法来求每个数欧拉函数时间复杂度是O(n*n^{\frac{1}{2}}),用筛法求每个数的欧拉函数只需要O(n)

//筛法求欧拉函数const int N = 100;
int primes[N], cnt; //primes存储素数,cnt用于计数
int eulers[N];       //存储每个数的欧拉函数
bool st[N];         //st判断该数是否被筛掉void get_eulers(int n)
{eulers[1] = 1;for (int i = 2; i <= n; i++){if (!st[i]){primes[cnt++] = i;eulers[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){eulers[t] = eulers[i] * primes[j];break;}eulers[t] = eulers[i] * (primes[j] - 1);}}
}

 四.快速幂

 

//求 m^ k mod p,时间复杂度 O(logk)。int qmi(int m, int k, int p)
{int result = 1;int t = m;while (k){if (k & 1)result = result * t % p;t = t * t % p;k >>= 1;}return result;
}

 五.扩展欧几里得算法

 

 

//扩展欧几里得算法
//ax + by = gcd(a,b),求x,y
//注意xy是&
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;
}

 六.用扩展欧几里得算法求线性同余方程

//扩展欧几里得算法
//ax + by = gcd(a,b),求x,y
//注意xy是&
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;
}int main()
{int n;scanf("%d", &n);while (n--){int a, b, m;scanf("%d %d %d", &a, &b, &m);int x = 0, y = 0;int d = exgcd(a, m, x, y);if (b % d != 0)printf("impossible\n");elseprintf("%d\n", (b / d) * x % m);}return 0;
}

 

这篇关于数学知识--(欧拉函数,快速幂,扩展欧几里得算法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/880025

相关文章

MySQL常用字符串函数示例和场景介绍

《MySQL常用字符串函数示例和场景介绍》MySQL提供了丰富的字符串函数帮助我们高效地对字符串进行处理、转换和分析,本文我将全面且深入地介绍MySQL常用的字符串函数,并结合具体示例和场景,帮你熟练... 目录一、字符串函数概述1.1 字符串函数的作用1.2 字符串函数分类二、字符串长度与统计函数2.1

python使用try函数详解

《python使用try函数详解》Pythontry语句用于异常处理,支持捕获特定/多种异常、else/final子句确保资源释放,结合with语句自动清理,可自定义异常及嵌套结构,灵活应对错误场景... 目录try 函数的基本语法捕获特定异常捕获多个异常使用 else 子句使用 finally 子句捕获所

postgresql使用UUID函数的方法

《postgresql使用UUID函数的方法》本文给大家介绍postgresql使用UUID函数的方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录PostgreSQL有两种生成uuid的方法。可以先通过sql查看是否已安装扩展函数,和可以安装的扩展函数

MySQL字符串常用函数详解

《MySQL字符串常用函数详解》本文给大家介绍MySQL字符串常用函数,本文结合实例代码给大家介绍的非常详细,对大家学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql字符串常用函数一、获取二、大小写转换三、拼接四、截取五、比较、反转、替换六、去空白、填充MySQL字符串常用函数一、

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)

MySql基本查询之表的增删查改+聚合函数案例详解

《MySql基本查询之表的增删查改+聚合函数案例详解》本文详解SQL的CURD操作INSERT用于数据插入(单行/多行及冲突处理),SELECT实现数据检索(列选择、条件过滤、排序分页),UPDATE... 目录一、Create1.1 单行数据 + 全列插入1.2 多行数据 + 指定列插入1.3 插入否则更

PostgreSQL中rank()窗口函数实用指南与示例

《PostgreSQL中rank()窗口函数实用指南与示例》在数据分析和数据库管理中,经常需要对数据进行排名操作,PostgreSQL提供了强大的窗口函数rank(),可以方便地对结果集中的行进行排名... 目录一、rank()函数简介二、基础示例:部门内员工薪资排名示例数据排名查询三、高级应用示例1. 每

全面掌握 SQL 中的 DATEDIFF函数及用法最佳实践

《全面掌握SQL中的DATEDIFF函数及用法最佳实践》本文解析DATEDIFF在不同数据库中的差异,强调其边界计算原理,探讨应用场景及陷阱,推荐根据需求选择TIMESTAMPDIFF或inte... 目录1. 核心概念:DATEDIFF 究竟在计算什么?2. 主流数据库中的 DATEDIFF 实现2.1

MySQL中的LENGTH()函数用法详解与实例分析

《MySQL中的LENGTH()函数用法详解与实例分析》MySQLLENGTH()函数用于计算字符串的字节长度,区别于CHAR_LENGTH()的字符长度,适用于多字节字符集(如UTF-8)的数据验证... 目录1. LENGTH()函数的基本语法2. LENGTH()函数的返回值2.1 示例1:计算字符串

PostgreSQL的扩展dict_int应用案例解析

《PostgreSQL的扩展dict_int应用案例解析》dict_int扩展为PostgreSQL提供了专业的整数文本处理能力,特别适合需要精确处理数字内容的搜索场景,本文给大家介绍PostgreS... 目录PostgreSQL的扩展dict_int一、扩展概述二、核心功能三、安装与启用四、字典配置方法