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

本文共 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)=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案例

发表评论

最新留言

哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年03月17日 02时14分10秒

关于作者

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

推荐文章

python2和3安装后怎样切换 mac_Mac下安装配置Python2和Python3并相互切换使用 2019-04-21
python错误代码40035_python-(matplotlib.pyplot)散点图轴的顺序错误 2019-04-21
java servlet 返回 web_javaWEB之Servlet 2019-04-21
php 打印出心形,利用php输出不同的心形图案_PHP 2019-04-21
php表格怎么加粉色,把知识点用表格形式表示出来,鼠标经过一行的时候背景颜色会变成粉色... 2019-04-21
oracle 时间戳样式,oracle日期时间型timestamp的深入理解 2019-04-21
linux命令column,Linux column命令详解(每日一令之二十一) 2019-04-21
centos linux7 开启桌面命令,centos7如何在桌面打开终端 2019-04-21
linux ha 磁盘心跳,HACMP 5.4配置磁盘心跳(转载) 2019-04-21
linux usb-skeleton,Linux USB驱动程序(4)----usb-skeleton.c分析 2019-04-21
C语言编程绘制一元二次函数,c语言怎么画出一元二次函数图像 2019-04-21
使用c 脚本语言制作菜单,VC动态生成菜单项的实现方法 2019-04-21
华为鸿蒙系统使用技巧,【图片】华为鸿蒙系统的厉害之处在于 你可能非用不可!【手机吧】_百度贴吧... 2019-04-21
Android输入法方法,Android的输入法系统框架原理 2019-04-21
android点击屏幕中间播放,android上,实现直接在屏幕上显示点击位置,方便调试。... 2019-04-21
winform编译android,拋物線之winform與android的實現 2019-04-21
android camera噪点,android位图上的噪点效果 2019-04-21
html js获取数组坐标,js怎么获取数组中元素的位置 2019-04-21
html在线拖拽环绕,html界面元素拖拽实现[超简单] 2019-04-21
html主题居中用什么命令,css中常用的几种居中方法(推荐) 2019-04-21