网站推广公司兴田德润,自己做网站代码,爱南宁app下载官网中小学,如何建网站看到物联网设备信息宣传一下 算法提高课整理
CSDN个人主页#xff1a;更好的阅读体验 原题链接
题目描述
求关于 x x x 的同余方程 a x ≡ 1 ( m o d b ) ax ≡ 1 \pmod b ax≡1(modb) 的最小正整数解。
输入格式
输入只有一行#xff0c;包含两个正整数 a , b a,b a,b#xff0c;用一…宣传一下 算法提高课整理
CSDN个人主页更好的阅读体验 原题链接
题目描述
求关于 x x x 的同余方程 a x ≡ 1 ( m o d b ) ax ≡ 1 \pmod b ax≡1(modb) 的最小正整数解。
输入格式
输入只有一行包含两个正整数 a , b a,b a,b用一个空格隔开。
输出格式
输出只有一行包含一个正整数 x x x表示最小正整数解。
输入数据保证一定有解。
数据范围 2 ≤ a , b ≤ 2 × 1 0 9 2 \le a,b \le 2 \times 10^9 2≤a,b≤2×109
输入样例
3 10输出样例
7思路
我们对 a x ≡ 1 ( m o d b ) ax ≡ 1 \pmod b ax≡1(modb) 进行变形
设 y ∈ R y \in \mathbb{R} y∈R则 a x ≡ 1 ( m o d b ) ⇔ a x − b y 1 ax \equiv1 \pmod b \Leftrightarrow ax-by1 ax≡1(modb)⇔ax−by1
我们知道扩展欧几里得算法可以计算形如 a x b y gcd ( a , b ) axby\gcd(a,b) axbygcd(a,b) 的方程的解。
所以直接进行转化即可。
注意 由于题目要求输出正整数解所以我们输出 ( x m o d p p ) m o d p (x \bmod p p) \bmod p (xmodpp)modp 即可。
算法时间复杂度 O ( log n ) O(\log n) O(logn)
AC Code C \text{C} C #include cstring
#include iostream
#include algorithmusing namespace std;typedef long long LL;LL exgcd(LL a, LL b, LL x, LL y)
{if (!b){x 1, y 0;return a;}LL d exgcd(b, a % b, y, x);y - a / b * x;return d;
}int main()
{LL a, b, x, y;cin a b;exgcd(a, b, x, y);cout (x % b b) % b endl;return 0;
}最后如果觉得对您有帮助的话点个赞再走吧
