APTX Blog

A Moe Blog Set By APTX

#洛谷#C/C++P1082 同余方程 逆元(欧拉函数)/拓展欧几里得

逆元

a * b = 1 (mod p) 则a,b互为逆元

费马小定理

a ^(p-1)  = 1 (mod p)

p 为质数

->   a * a ^(p-2)  = 1 (mod p)

于是 a和a ^(p-2) 互为逆元

欧拉函数

定义:φ(x)=x(1-1/p(1))(1-1/p(2))(1-1/p(3))(1-1/p(4))…..(1-1/p(n))      p(1),p(2)…p(n)为x的所有质因数

表示 小于x的数中与x互质的数的数目

欧拉公式:a ^ φ(p)  =1 (mod p)

-> a * a ^ (φ(p)  -1)  =1 (mod p)

a与 a ^ (φ(p)  -1) 互为逆元

题目描述

求关于 x 的同余方程 ax1(modb) 的最小正整数解。

输入输出格式

输入格式:

一行,包含两个正整数 a ,用一个空格隔开。

输出格式:

一个正整数 x0 ,即最小正整数解。输入数据保证一定有解。

输入输出样例

输入样例#1:

输出样例#1:

关于本题

ax1(modb)

由欧拉函数 a * a ^ (φ(b)  -1)=1 (mod b)

即求a ^ φ(b-1) 即可

本人提供的题解

拓展欧几里得和欧拉函数两种解法

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注