本文共 7900 字,大约阅读时间需要 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)=n−1
朴素法求欧拉函数 :
模版 : 给定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 ap−aap−a是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}} ap≡a(modp)ap≡a(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}} ap−1≡1(modp)ap−1≡1(modp)
这个书写方式更加常用。
筛法求欧拉函数 :
原理 : 线性筛 + 欧拉函数公式 :
模版 : 给定一个正整数 n , 求 1 ~ n 中每个数的欧拉函数之和
特殊情况 : 当一个数 x 为质数时 , 其欧拉函数为 ϕ ( x ) = x − 1 \phi(x) = x - 1 ϕ(x)=x−1 ( 1 ~ n-1 )
分三种情况 :
- i 为质数时 , 其欧拉函数为 ϕ ( x ) = x − 1 \phi(x) = x - 1 ϕ(x)=x−1 ( 1 ~ n-1 )
- i % P j P_j Pj == 0 时 , ϕ ( P j ∗ i ) = P j ∗ ϕ ( i ) \phi(P_j * i) = P_j * \phi(i) ϕ(Pj∗i)=Pj∗ϕ(i)
- i % P j P_j Pj != 0 时 , ϕ ( P j ∗ i ) = ϕ ( i ) ∗ ( P j − 1 ) \phi(P_j * i) = \phi(i) * (P_j - 1) ϕ(Pj∗i)=ϕ(i)∗(Pj−1)
代码如下 :
// 筛法求欧拉函数// 给定一个正整数 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) an−1=1(modn) , n 为 质数时 , ϕ ( n ) = n − 1 \phi(n) = n - 1 ϕ(n)=n−1 , 此推论又称为费马定理
快速幂
简介: 快速幂,二进制取幂(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=38⋅34⋅31 因为 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 的逆元,记作 a−1。
详细定义 及 存在性 :
乘法逆元的定义:若存在正整数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) ai⋅xi+bi⋅yi=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) ai∗xi=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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!