欧拉函数快速幂扩展欧几里得算法中国剩余定理
发布日期:2022-02-24 01:06:49 浏览次数:1 分类:技术文章

本文共 7862 字,大约阅读时间需要 26 分钟。

欧拉函数快速幂扩展欧几里得算法中国剩余定理

欧拉函数(Euler)

互质 : 互质是公约数只有1的两个整数,叫做互质整数。 公约数只有1的两个自然数,叫做互质自然数,后者是前者的特殊情形。

定义: ϕ ( n ) \phi(n) ϕ(n) 表示的是小于等于n和n互质的数的个数, 也就是 1 ~ n中与n互质的数

ex : $\phi(6) = 2 , 1 , 5 $

当 n 是质数的时候 , 显然有 ϕ ( n ) = n − 1 \phi(n) = n - 1 ϕ(n)=n1

朴素法求欧拉函数 :

模版 : 给定n个正整数 , 请你求出每个数的欧拉函数.

代码如下 :

// 给定 n 个正整数 $a_i$ , 求出每个数的欧拉函数#include 
   
    #include 
    
     using namespace std ;int main(){

     
   int n ; cin >> n ;
while (n -- )
{
   int a ; cin >> a ;
int res = a ;
// 分解质因数 + 欧拉函数
for (int i = 2;i <= a / i; i ++ )
{
   if (a % i == 0)
{
   res = res / i * (i - 1) ;
while (a % i == 0) a /= i ;
}
}
if (a > 1) res = res / a * (a - 1) ;
cout << res << endl ;
}
return 0 ;}

欧拉函数也用来证明费马小定理 :

费马小定理是数论中的一个定理:假如 a a {\displaystyle a}a aa是一个整数, p p {\displaystyle p}p pp是一个质数,那么 a p − a a p − a {\displaystyle a^{p}-a}a^{p}-a apaapa是p的倍数,可以表示为

a p ≡ a ( m o d p ) a p ≡ a ( m o d p ) {\displaystyle a^{p}\equiv a{\pmod {p}}}a^{p}\equiv a{\pmod {p}} apa(modp)apa(modp)
如果a不是p的倍数,这个定理也可以写成

a p − 1 ≡ 1 ( m o d p ) a p − 1 ≡ 1 ( m o d p ) {\displaystyle a^{p-1}\equiv 1{\pmod {p}}}a^{ {p-1}}\equiv 1{\pmod {p}} ap11(modp)ap11(modp)
这个书写方式更加常用。

筛法求欧拉函数 :

原理 : 线性筛 + 欧拉函数公式 :

模版 : 给定一个正整数 n , 求 1 ~ n 中每个数的欧拉函数之和

特殊情况 : 当一个数 x 为质数时 , 其欧拉函数为 ϕ ( x ) = x − 1 \phi(x) = x - 1 ϕ(x)=x1 ( 1 ~ n-1 )

分三种情况 :

  1. i 为质数时 , 其欧拉函数为 ϕ ( x ) = x − 1 \phi(x) = x - 1 ϕ(x)=x1 ( 1 ~ n-1 )
  2. i % P j P_j Pj == 0 时 , ϕ ( P j ∗ i ) = P j ∗ ϕ ( i ) \phi(P_j * i) = P_j * \phi(i) ϕ(Pji)=Pjϕ(i)
  3. i % P j P_j Pj != 0 时 , ϕ ( P j ∗ i ) = ϕ ( i ) ∗ ( P j − 1 ) \phi(P_j * i) = \phi(i) * (P_j - 1) ϕ(Pji)=ϕ(i)(Pj1)

代码如下 :

// 筛法求欧拉函数// 给定一个正整数 n , 求 1 ~ n 中每个数的欧拉函数之和#include 
   
    #include 
    
     using namespace std ;typedef long long LL ;const int N = 100010 ;int primes[N] , cnt ; bool st[N] ;int phi[N] ;LL get_euler(int n){

     
   phi[1] = 1 ;
for (int i = 2;i <= n;i ++ )
{
   if (!st[i])
{
primes[cnt ++ ] = i ;
 phi[i] = i - 1 ;
}
for (int j = 0;primes[j] <= n / i;j ++ )
{
   st[primes[j] * i] = true ;
if (i % primes[j] == 0)
{
   phi[primes[j] * i] = primes[j] * phi[i] ;
break ;
}
phi[primes[j] * i] = phi[i] * (primes[j] - 1) ;
}
}
LL res = 0 ;
for (int i = 1;i <= n;i ++ ) res += phi[i] ;
return res ;}int main(){
   int n ; cin >> n ;
cout << get_euler(n) << endl ;
return 0 ;}

欧拉定理 :

若 a 与 n 互质 , 则 a ϕ ( n ) = 1 ( m o d n ) {a^{\phi(n)}} = 1 (mod n) aϕ(n)=1(modn)

ex : a = 5 , n = 6 , ϕ ( n ) = 2 \phi(n) = 2 ϕ(n)=2 , a 2 a^2 % n = 25 % 6 == 1 a2

证明 :

推论(特例) :

当 n 为质数时 , a n − 1 = 1 ( m o d n ) a^{n-1} = 1 (mod n) an1=1(modn) , n 为 质数时 , ϕ ( n ) = n − 1 \phi(n) = n - 1 ϕ(n)=n1 , 此推论又称为费马定理

快速幂

简介: 快速幂,二进制取幂(Binary Exponentiation,也称平方法),是一个在 O (log n) 的时间内计算 a^n 的小技巧,而暴力的计算需要 O( n ) 的时间。而这个技巧也常常用在非计算的场景,因为它可以应用在任何具有结合律的运算中。其中显然的是它可以应用于模意义下取幂、矩阵幂等运算.

常规快速幂 :

二进制取幂的想法是,我们将取幂的任务按照指数的 二进制表示 来分割成更小的任务。

首先我们将

首先我们将 表示为 2 进制,举一个例子:
3 13 = 3 ( 1101 ) 2 = 3 8 ⋅ 3 4 ⋅ 3 1 3^{13} = 3^{(1101)_2} = 3^8 \cdot 3^4 \cdot 3^1 313=3(1101)2=383431
因为 n 有 l o g 2 n + 1 log_2n + 1 log2n+1 个二进制位 , 因此当我们知道了 a 1 , a 2 , . . . , a l o g 2 n a^1 , a^2 , ... , a^{log_2 n} a1,a2,...,alog2n 后 , 我们只用计算 O(log n) 次乘法就可以计算出 a^n

给定n组 a i b i p i a_i b_i p_i aibipi , 对于每组数据 , 求出 a i b i m o d p i {a_i}^{b_i} mod {p_i} aibimodpi 的值

a^k mod p

时间复杂度 : O (log k)

核心思路 : 反复平方法

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Ax1skPyh-1605099228170)(…/…/…/…/tygatyga/Typora/images/image-20201030092353314.png)]

每一个数都是其前一个数的平方 , 不断平方即可得到预处理结果

步骤 : 先预处理 1 ~ logk 个数 mod p 的结果 , 再将 k 转化为 二进制 , 将对应的二进制的余数相乘即可得到结果

ex :

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qGnbg14u-1605099228172)(…/…/…/…/tygatyga/Typora/images/image-20201030092913679.png)]

代码如下 :

// 给定n组 $a_i b_i p_i$ , 对于每组数据 , 求出 ${a_i}^{b_i} mod {p_i}$ 的值#include 
   
    #include 
    
     using namespace std ;typedef long long LL ; // 有乘积 , 会爆int , 用 long long// a^k mod pint qmi(int a,int k,int p){

     
   int res = 1 ;
while (k)
{
   if (k & 1) res = (LL)res * a % p ; // 看个位为1还是0 为1乘上 否则不乘
k >>= 1 ; // 取 下一位
a = (LL)a * a % p ;  // a 取 下一位 即平方
}
return res ;}int main(){
   int n ;
scanf("%d",&n) ;
while (n -- )
{
   int a, k, p ;
scanf("%d%d%d",&a, &k, &p) ; // 当读入多组数据时用 scanf较好
printf("%d\n",qmi(a,k,p)) ;
}
return 0 ;}

快速幂的应用 : 求逆元

题目描述 :

给定 n 组 a i , p i a_i , p_i ai,pi , 其中 p i p_i pi 是质数 , 求 a i m o d p i a_i mod p_i aimodpi的乘法逆元 , 若不存在则输出 impossible

乘法逆元的定义1 :

如 果 一 个 线 性 同 余 方 程   a x = 1   ( m o d   b ) , 则   x   称 为   a   m o d   b   的 逆 元 , 记 作   a − 1 。 如果一个线性同余方程 \ ax = 1 \ (mod \ b),则\ x\ 称为\ a\ mod\ b\ 的逆元,记作\ a^{-1}。 线 ax=1 (mod b) x  a mod b  a1

详细定义 及 存在性 :

乘法逆元的定义:若存在正整数a,b,p, 满足ab = 1(mod p), 则称a 是b 的乘法逆元, 或称b 是a 的乘法逆元。b ≡ a-1 (mod p),a ≡ b-1 (mod p)

比如说, 在模7 意义下,3 的乘法逆元是5, 也可以说模7 意义下5的乘法逆元是3。模13意义下5的逆元是8……

乘法逆元的存在性:在同余方程中 ab ≡ 1(mod p)

若a 与p 互质, 则一定存在一个正整数解b, 满足b < p,若a 与p 不互质, 则一定不存在正整数解b.

所以逆元要求a与p互质

如果 a / b 是一个整数的话 , 我们希望 a / b 同余于 a * x (mod m) 任务 : 找到这个 x , x 叫做 b 模 m 的逆元

记作 : a / b 同余于 a * b的逆元 (mod m)

b 和 p 不互质的话就一定无解

代码如下 :

#include 
   
    #include 
    
     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 t ; cin >> t ;
while (t -- )
{
   int a , p ; scanf("%d%d",&a,&p) ;
int res = qmi(a, p-2, p) ;
if (a % p) printf("%d\n",res) ; // a . p 互质
else puts("impossible") ;
}
return 0 ;}

扩展欧几里得算法

回顾 : 欧几里得算法 – 辗转相除法 – gcd

预备知识 : 裴蜀定理

裴蜀定理,又称贝祖定理(Bézout’s lemma)。是一个关于最大公约数的定理。

其内容是:

对于任意正整数 a , b

设 a,b 是不全为零的整数,则存在非零整数 x,y , 使得 ax + by = gcd(a,b)

ax + by = d , d一定是 a,b的倍数

扩展欧几里得算法(exgcd) :

构造 a,b x,y , 求出 x,y

模版 :

给定 n 正整数 a i , b i a_i , b_i ai,bi , 对于每对数 , 求出一组 x i , y i x_i , y_i xi,yi , 使其满足
a i ⋅ x i + b i ⋅ y i = g c d ( a i , b i ) a_i \cdot x_i + b_i \cdot y_i = gcd(a_i,b_i) aixi+biyi=gcd(ai,bi)

a % b = a - a/b(下取整) * b 解释: a除以b 得到的余数等于 a 减去 a 除 b 的商乘上b

代码如下 :

#include 
   
    #include 
    
     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 , y , x ) ; // b 和 a交换位置的同时 , y 与 x 也需交换位置
y -= a / b * x ; // 系数 y 需发生变化 ;
 return d ;}int main(){
   int n ; scanf("%d", &n) ;
while (n -- )
{
   int a, b , x , y ;
scanf("%d%d", &a, &b) ;
exgcd(a,b,x,y) ;
printf("%d %d\n", x , y ) ;
}
return 0  ;}

应用 : 求解线性同余方程

题目描述 :

给定 n 组数据 a i , b i , m i a_i , b_i , m_i ai,bi,mi , 对于每组数 , 求出一个 x i x_i xi , 使其满足 a i ∗ x i = b i ( m o d m i ) a_i * x_i = b_i(mod m_i) aixi=bi(modmi) , 如果无解则输出 impossible

输入 :

2

2 3 6

4 3 5

输出 :

impossible

7

可能 存在一个数 z , 使得 : ax = my + b

ax - my = b

ax + my` = b

代码如下:

#include 
   
    #include 
    
     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 , 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,  y ;
int d = exgcd(a , m , x , y ) ;
if (b % d ) puts("impossible") ;
else printf("%d\n",(LL)x * (b / d) % m ) ;
}
return 0 ;}

中国剩余定理

模版 :

给定 2n 个整数 a 1 , a 2 . . a n a_1,a_2 .. a_n a1,a2..an m 1 , m 2 . . m n m_1 , m_2 .. m_n m1,m2..mn , 求一个最小的整数 x , 满足 对于任意的 1~n ,

x 同余于 m i m_i mi(mod a i a_i ai) 都成立

输入样例 :

2

8 7

11 9

输出样例 :

31

代码如下 :


 

转载地址:https://blog.csdn.net/weixin_45877540/article/details/109133140 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:python的执行
下一篇:java简单实用的阿里云短信验证码后端API案例

发表评论

最新留言

路过按个爪印,很不错,赞一个!
[***.36.148.67]2022年06月21日 20时11分21秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章

java gui 结构_java GUI编程 2019-12-01 15:24:36
java 单件_Java语言设计模式学习之单件模式实例讲解 2019-12-01 15:24:37
java在密码错误时不跳转页面_javaweb利用ajax使登录窗口不跳转页面实现对账号密码的判断... 2019-12-01 15:24:37
java类变量调用_JAVA类的方法调用和变量(全套) 2019-12-01 15:24:37
mysql 清理归档日志_oracle归档日志清理 2019-12-01 15:24:37
interrupt java_关于java中的interrupt 2019-12-01 15:24:37
什么是java环境变量_什么是java环境变量 2019-12-01 15:24:38
chttpconnection 系统找不到指定文件_Win7系统安装MySQL之后找不到指定文件与服务如何解决?... 2019-12-01 15:24:35
ad湿度传感器的流程图_「雕爷学编程」Arduino动手做(08)——湿度传感器模块... 2019-12-01 15:24:35
vue前端_8.1 SRE 要懂点前端vue 2019-12-01 15:24:35
linux系统mysql入侵_Linux高级入侵检测-文件系统完整性 2019-12-01 15:24:35
mysql 唯一索引出现重复数据_mysql使用唯一索引避免插入重复数据 2019-12-01 15:24:35
mysql实现评论盖楼的sql_mysql - 网易的评论盖楼设计,用php的话,应该怎样实现?怎样存入数据库?... 2019-12-01 15:24:36
java多线程生产者消费者问题_java多线程解决生产者消费者问题 2019-12-01 15:24:36
c 批量更新mysql数据库_MySql批量更新方式大全 2019-12-01 15:24:33
autowarid和resources_ÂÐÏØÈË´ó 2019-12-01 15:24:33
python函数的定义教程_Python函数定义、函数调用详解 2019-12-01 15:24:33
python合并相同索引列表_python – 按行和相同的索引pandas合并两个数据帧 2019-12-01 15:24:33
ssis抽MySQL数据_微软SSIS部署抽取数据的包报错 2019-12-01 15:24:34
whmcs 添加域名_WHMCS域名更换教程 2019-12-01 15:24:34