首页 > 代码库 > 扩展欧几里得
扩展欧几里得
题目描述
求关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解。
输入输出格式
输入格式：
输入只有一行，包含两个正整数 a, b，用一个空格隔开。
输出格式：
输出只有一行，包含一个正整数 x0，即最小正整数解。输入数据保证一定有解。
1 #include < bits/stdc++.h > 2 3 using namespace std; 4 5 int a, b, x, y, gcd; 6 7 inline int exgcd(int a, int b, int &x, int &y){ 8 if(!b){ 9 x = 1, y = 0; 10 return a;11 }12 int r = exgcd(b, a % b, y, x);13 y -= a / b * x;14 return r;15 }16 17 int main(){18 scanf("%d %d", &a, &b);19 gcd = exgcd(a, b, x, y);20 printf("%d", (x % b + b) % b);21 return 0;22 }
完事。
扩展欧几里得
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。