题目描述 Description

求关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解。

输入输出格式 Input/output

输入格式：

输入只有一行，包含两个正整数 a, b，用一个空格隔开。

输出格式：

输出只有一行，包含一个正整数 x0，即最小正整数解。输入数据保证一定有解。

输入：3 7 

输出：10

题解：这道题我们先要看懂题意。题目的意思就是ax mod b=1，也就是ax-kb=1。考虑扩展的欧几里得定理。显然y可以是一个负值，我们的目的就是求一个最小的正整数x，让ax比b的某个整数倍大1。

题目意思即：ax=1+by，也即ax-by=1。

代码：

#include"iostream"#include"cstdio" #include"cstdlib" #include"cstring" #include"algorithm"using namespace std; long long a,b,x,y; long long extended_gcd(long long  a,long long b,long long &x,long long &y) {     if (!b) { x=1; y=0; return a; }     else    {              long long ans=extended_gcd(b,a%b,x,y);              long long t=x; x=y; y=t-(a/b)*y;             return ans;     } } int main() {     cin >> a >> b;     long long ans = extended_gcd(a, b, x, y);           x=x%b;     while (x<0) x+=b;     //我们求出的x是a的整数倍，这个整数倍可以是负值。但要求是最小整数倍    //所以我们将x加上b，因为加上之后还可以满足要求，即ax mod b=1。    cout << x << endl;       return 0; }