显然这是一道裸的数论题目。 -第一，题目中让我们求的是最小正整数解，而我们使用的算法最后得出的结果可能为负数，这就需要我们在最后得出结果时，加一个整数再去模b，即输出结果时用以下语句：cout<<(x+b)%b;这样我们就得到一个最小正整数解了！ -第二，问题的转化。 可能对我这种数论渣渣，理解楼下题解的话花了不少时间...在这里为同样和我蒻的同学说明一下。 首先解释一下平时在数学课本上不出现的符号≡，同余符号，含义为两个整数a，b，若它们除以整数m所得的余数相等，则称a，b对于模m同余，记作a≡b(mod m)。 那么，同余方程ax ≡ 1 (mod b)，如果转化为我们通俗易懂的语言就是->求满足ax%b=1，1%b=1最小正整数解。 那么接下来就可以使用扩展欧几里得解决了。 -第三，楼下题解中，很多代码都是这种形式 int exgcd(int a,int b,int &x,int &y) 而天真的我没有加上“&”符号，这就导致了我的程序Wa掉了... int exgcd(int a,int b,int x,int y) 翻阅了评论区，看到一个dalao HanayoOI告诉我们说：扩展欧几里德需要修改x,y变量本身来实现。 而不加“&”符号，那么在exgcd执行完后x和y不会被修改。 我们可以把x,y设置为全局变量，这样就可以避免一些麻烦。 那么，我们就可以得到如下代码： #include #include using namespace std;   int a,b,x,y,k;   void exgcd(int a,int b) { if(b==0) { x=1; y=0; return; } exgcd(b,a%b); k=x; x=y; y=k-a/b*y; return; }   int main() { cin>>a>>b; exgcd(a,b); cout<<(x+b)%b; }