这道题求关于x的同余方程ax≡1(mod b)的最小正整数解。换而言之方程可以转换为ax+by=1,此时有y为负数。此时当且仅当gcd(a,b)|1时,方程有整数解。
于是乎这道题就变成了ax+by=gcd(a,b)即扩展欧几里得问题。如何解决这个问题呢?
由gcd的基本性质可以得出:gcd(b,a%b)=gcd(a,b),这个值我们设为g。既有ax+by=g,bx+(a%b)y=g,变形得,bx+(a-a/b*b)y=g,展开得ay+b(x-y*a/b)=g,此时显而易见有一组解为:x=y1,y=x-y*a/b
那么所有的解都可以由于后面的解得出,于是用递归实现。
//#include<fstream>
//#include<cmath>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<queue>
//#include<vector>
//#include<stack>
//#include<map>
using namespace std;
long long read(){
long long res=,f=;
char ch=getchar();
while(ch<''||ch>''){
if(ch=='-')f=-;
ch=getchar();
}
while(ch>=''&&ch<=''){
res=res*+(ch-'');
ch=getchar();
}
return res*f;
}
//ax+by=gcd(a,b);
long long x,y,xt;
long long a,b;
void exgcd(int a,long long b){
if(b==){
x=;y=;
return;
}
exgcd(b,a%b);
xt=x;
x=y;
y=xt-a/b*y;
}
int main(){
a=read();b=read();
exgcd(a,b);
while(x<)x+=b;
x%=b;
cout<<x;
return ;
}