【题目来源】
洛谷：P1082 [NOIP 2012 提高组] 同余方程 - 洛谷
【题目描述】
求关于 \(x\) 的同余方程 \(ax≡1(modb)\) 的最小正整数解。
【输入】
一行，包含两个整数 \(a,b\)，用一个空格隔开。
【输出】
一个整数 \(x_0\)，即最小正整数解。输入数据保证一定有解。
【输入样例】
3 10
【输出样例】
7
【算法标签】
《洛谷 P1082 同余方程》 #数学# #扩展欧几里得算法# #NOIP提高组# #2012#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int a, b; // 输入的两个整数
int x, y; // 存储扩展欧几里得算法解出的系数// 扩展欧几里得算法
void exgcd(int a, int b)
{// 递归终止条件：b为0时，gcd(a,0)=aif (b == 0){x = 1; // 此时x=1y = 0; // y=0（可以是任意值，通常取0）return;}// 递归调用，交换a和b的位置exgcd(b, a % b);// 回溯时更新x和y的值int t = y; // 保存上一层的y值y = x - a / b * y; // 计算当前层的y值x = t; // 当前层的x值等于上一层的y值return;
}int main()
{// 输入两个整数a和bcin >> a >> b;// 调用扩展欧几里得算法exgcd(a, b);// 将x调整为最小正整数解x = (x % b + b) % b;// 输出结果（a关于模b的乘法逆元）cout << x << endl;return 0;
}
【运行结果】
3 10
7