第四章 数学知识 (二)(欧拉函数、快速幂、扩展欧几里得、中国剩余定理)

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

一、欧拉函数(1~n中有多少个数和n互质)

(一) 1~n 中和n互质的数

        1、互质数:公约数为1的两个整数。

        2、当n为6的时候:

        3、容斥原理公式

                                                 

           

                                 

        4、定义法求某一个数的欧拉函数

#include<bits/stdc++.h>
//873 欧拉函数用公式定义法求某个数的欧拉函数
using namespace std;
int n;
int main()
{cin>>n;while(n--){int a;cin>>a;int res=a;for(int i=2;i<=a/i;i++)//质数分解{if(a%i==0){//根据公式(1-1/i)变形res=res/i*(i-1);while(a%i==0)a/=i;}}if(a>1)res=res/a*(a-1);cout<<a<<endl;}
}

            5、筛法求欧拉函数,求1-n中某一个数的欧拉函数

                      求1~n中欧拉函数的和。质数的欧拉函数为n-1。

                      利用线性筛法,每次遍历到的st为false的数(质数)可以直接算出来欧拉函数;在遍  历之前的所有素数筛掉合数的时候,

#include<bits/stdc++.h>
//874 筛法求欧拉函数 求1-n的欧拉函数的和
using namespace std;
typedef long long LL;
const int N=1e6+10;
int prime[N],phi[N],idx,st[N];//分别记录素数、欧拉函数、是否被筛选掉
LL  get_eulers(int n)
{//从2开始算的phi[1]=1;//这里i不是数组的下标是真正遍历到的数for(int i=2;i<=n;i++){//素数if(!st[i])phi[i]=i-1,prime[idx++]=i;for(int j=0;prime[j]<=n/i;j++){st[i*prime[j]]=true;if(i%prime[j]==0){//pj是i的最小质因数,所以欧拉函数的结果只乘pj即可phi[i*prime[j]]=prime[j]*phi[i];break;}//如果不是需要乘以pj*(1-1/pj)phi[i*prime[j]]=phi[i]*(prime[j]-1);}}LL res=0;for(int i=0;i<=n;i++)res+=phi[i];return res;
}
int main()
{int n;cin>>n;cout<<get_eulers(n);return 0;
}

(二) 欧拉定理

当n和p互质的时候(费马定理)

(可证)p mod n(p除n的余数)与n互质。若此结论成立,则也有 pi ≡ xj(mod n)。

二、快速幂(O(log k)快速求出a^k mod p)

(一)快速幂基础算法实现

1、求法:将k分解为多个 (2^x1+……)相加的结果。只需要计算以a为底 2^xi次方为指数的值的乘积。  

计算单个的时候,每一个都是上一个的平方。

4^5举例:要知道存在一个对应的等价关系:将k分解为二进制相加的形式,目的就是为了转换为以a为底的数的乘法,累计得到结果。每次循环都更新a。

                                    

快速幂计算

#include<bits/stdc++.h>
//875 快速幂
using namespace std;
typedef long long LL;
int qmi(int a,int k,int p)
{int res=1;while(k){//注意判断某个数的二进制最后一位的值的方法if(k&1)res=(LL)res*a%p;k>>=1;a=(LL)a*a%p;}return res;
}
int main()
{int n;cin>>n;while(n--){int a,k,p;cin>>a>>k>>p;cout<<qmi(a,k,p)<<endl;}
}

(二)、快速幂求逆元(求逆元可以转化为求快速幂)

 如果b可以整除a,整除后的结果可以找到一个x使得a*x在mod m的情况下相同。x为b的模m逆元。

也就是可以把除以b转换为乘以b的逆元的情况。

                                

                             

 转化为求下列式子的x的值。

                          

根据费马小定理(若b和p互质)

                               

无解的情况:b是p的倍数的时候无解

#include<bits/stdc++.h>
//876 快速幂求逆元
using namespace std;
typedef long long LL;
int qmi(int a,int k,int p)
{int res=1;while(k){//注意判断某个数的二进制最后一位的值的方法if(k&1)res=(LL)res*a%p;k>>=1;a=(LL)a*a%p;}return res;
}
int main()
{int n;cin>>n;while(n--){int b,p;cin>>b>>p;int res=qmi(b,p-2,p);//注意判断是否有结果的条件if(b%p)cout<<res<<endl;else puts("impossible");}
}

三、扩展欧几里得算法

(一)裴蜀定理

(a,b)为ab的最大公约数。

由于ab凑出来的数一定是最大公约数的倍数。一定可以凑出这个最大公约数

877求xy(x,y)是不唯一的。

扩展欧几里得求解xy。还是递归的思想,如果b==0,最大公因数为a,x=1,y=0;结束即可;

递归就要明白两层之间的关系,与欧几里得算法类似,ax+by=gcd 的下一层是bx1+a%b y1=gcd;我们先得到的x1和y1,然后用找x1 y1和x y的关系,化简上面的式子 得到 ay1+b(x1-(a/b)*y1)=gcd

得到两层之间的关系。

#include<bits/stdc++.h>
//877 扩展欧几里得算法求xy
using namespace std;
typedef long long LL;
int exgcd(int a,int b,int &x,int &y)
{if(!b)//递归结束标志{x=1,y=0;return a;}int d=exgcd(b,a%b,x,y);//交换的意思是上一层的x1y1导到了这一层//会变成yx,此时x已经更新到位,并进一步更新y。int t=x;x=y;y=t;y-=(a/b)*x;
}
int main()
{int n,x,y;cin>>n;while(n--){int a,b;cin>>a>>b;exgcd(a,b,x,y);cout<<x<<" "<<y;}
}

(二)扩欧应用:求解线性同余方程

知道 a、b 、m求解x。

只要b是a和m的最大公约数的倍数就一定有解。

先按照结果为最大公约数算,如果b不是最大公约数的倍数,就无解,

#include<bits/stdc++.h>
//878 线性同余方程
using namespace std;
typedef long long LL;
int exgcd(int a,int b,int &x,int &y)
{if(!b)//递归结束标志{x=1,y=0;return a;}int d=exgcd(b,a%b,x,y);//交换的意思是上一层的x1y1导到了这一层//会变成yx,此时x已经更新到位,并进一步更新y。int t=x;x=y;y=t;y-=(a/b)*x;return d;
}
int main()
{int n,x,y;cin>>n;while(n--){int a,b,m;cin>>a>>b>>m;int x,y;int ans=exgcd(a,m,x,y);if(b%ans)puts("impossible");//目前式子求的是相加结果为最大公约数的结果//x需要再乘以(b/ans)mod melse cout<<x*(b/ans)%m<<endl;}
}

四、中国剩余定理

m两两互斥,要求大括号里面成立,Mi^-1表示Mi以mi为模的逆。Mi是除了mi之外的所有m的乘积。最后得到的x的式子是满足所有的前面大括号的条件的。

这篇关于第四章 数学知识 (二)(欧拉函数、快速幂、扩展欧几里得、中国剩余定理)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Spring AI与DeepSeek实战一之快速打造智能对话应用

《SpringAI与DeepSeek实战一之快速打造智能对话应用》本文详细介绍了如何通过SpringAI框架集成DeepSeek大模型,实现普通对话和流式对话功能,步骤包括申请API-KEY、项目搭... 目录一、概述二、申请DeepSeek的API-KEY三、项目搭建3.1. 开发环境要求3.2. mav

Python如何快速下载依赖

《Python如何快速下载依赖》本文介绍了四种在Python中快速下载依赖的方法,包括使用国内镜像源、开启pip并发下载功能、使用pipreqs批量下载项目依赖以及使用conda管理依赖,通过这些方法... 目录python快速下载依赖1. 使用国内镜像源临时使用镜像源永久配置镜像源2. 使用 pip 的并

Java8需要知道的4个函数式接口简单教程

《Java8需要知道的4个函数式接口简单教程》:本文主要介绍Java8中引入的函数式接口,包括Consumer、Supplier、Predicate和Function,以及它们的用法和特点,文中... 目录什么是函数是接口?Consumer接口定义核心特点注意事项常见用法1.基本用法2.结合andThen链

MySQL 日期时间格式化函数 DATE_FORMAT() 的使用示例详解

《MySQL日期时间格式化函数DATE_FORMAT()的使用示例详解》`DATE_FORMAT()`是MySQL中用于格式化日期时间的函数,本文详细介绍了其语法、格式化字符串的含义以及常见日期... 目录一、DATE_FORMAT()语法二、格式化字符串详解三、常见日期时间格式组合四、业务场景五、总结一、

golang panic 函数用法示例详解

《golangpanic函数用法示例详解》在Go语言中,panic用于触发不可恢复的错误,终止函数执行并逐层向上触发defer,最终若未被recover捕获,程序会崩溃,recover用于在def... 目录1. panic 的作用2. 基本用法3. recover 的使用规则4. 错误处理建议5. 常见错

SpringBoot快速接入OpenAI大模型的方法(JDK8)

《SpringBoot快速接入OpenAI大模型的方法(JDK8)》本文介绍了如何使用AI4J快速接入OpenAI大模型,并展示了如何实现流式与非流式的输出,以及对函数调用的使用,AI4J支持JDK8... 目录使用AI4J快速接入OpenAI大模型介绍AI4J-github快速使用创建SpringBoot

使用Python快速实现链接转word文档

《使用Python快速实现链接转word文档》这篇文章主要为大家详细介绍了如何使用Python快速实现链接转word文档功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 演示代码展示from newspaper import Articlefrom docx import

Python itertools中accumulate函数用法及使用运用详细讲解

《Pythonitertools中accumulate函数用法及使用运用详细讲解》:本文主要介绍Python的itertools库中的accumulate函数,该函数可以计算累积和或通过指定函数... 目录1.1前言:1.2定义:1.3衍生用法:1.3Leetcode的实际运用:总结 1.1前言:本文将详

轻松上手MYSQL之JSON函数实现高效数据查询与操作

《轻松上手MYSQL之JSON函数实现高效数据查询与操作》:本文主要介绍轻松上手MYSQL之JSON函数实现高效数据查询与操作的相关资料,MySQL提供了多个JSON函数,用于处理和查询JSON数... 目录一、jsON_EXTRACT 提取指定数据二、JSON_UNQUOTE 取消双引号三、JSON_KE

MySQL数据库函数之JSON_EXTRACT示例代码

《MySQL数据库函数之JSON_EXTRACT示例代码》:本文主要介绍MySQL数据库函数之JSON_EXTRACT的相关资料,JSON_EXTRACT()函数用于从JSON文档中提取值,支持对... 目录前言基本语法路径表达式示例示例 1: 提取简单值示例 2: 提取嵌套值示例 3: 提取数组中的值注意