ax
1
+by
1
=ax
2
+by
2
a(x
1
-x
2
)=b(y
2
-y
1
)
然后我们知道gcd(a,b)为a,b的最大公因数，所以我们将 A=a/gcd(a,b)，B=b/gcd(a,b)，接着往下推出
A(x
1
-x
2
)=B(y
2
-y
1
)
现在A和B两个已经是
互素
了,所以又可以接着推出
(这个地方要好好理解，重点！
)
A*(n*B)=B*(n*A)
(x
1
-x
2
)=n*B
(y
2
-y
1
)=n*A
这里我们从x入手
(x
1
-x
2
)=n*B
x
1
=x
2
+n*B
由此，我们推出了x解的通解公式
x=x
0
+n*B
同理，我们推出了y解的通解公式
y=y
0
-m*A
那么我们如果要求 x 的最小整数解,也就是 x
0
, 就是 x
0
=x%B
如果我们要求的是 ax+by=c，还得
先转化 x=x*c/gcd(a,b).
然后套入我们的公式
B=b/gcd(a,b)
x
0
=x%(b/gcd(a,b))
嗯，到此结束，下面给下实现代码
#include <bits/stdc++.h>
#include<unordered_set>
//freopen("in.txt", "r", stdin);
using namespace std;
typedef double dou;
typedef long long ll;
typedef pair<ll, ll> pii;
#define M 1050
#define inf 0x3f3f3f3f
#define mod 1000000007
#define W(a) while(a)
#define lowbit(a) a&(-a)
#define left k<<1
#define right k<<1|1
#define ms(a,b) memset(a,b,sizeof(a))
#define debug(a) cout<<#a<<" == "<<a<<endl
#define false_stdio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) {
x = 1, y = 0;
return a;
ll ans = exgcd(b, a%b, y, x);
y -= a / b * x;
return ans;
ll solve(ll a, ll b, ll c) {
ll x, y, z;
z = exgcd(a, b, x, y);
if (c%z)return -1;//不成立
//return x; //不需要最小正整数的话直接返回x
x *= c / z;
b = abs(b / z);
return (x%b + b) % b;
int main() {
false_stdio;
ll a, b, c;
cin >> a >> b >> c;
ll x = solve(a, b, c);
ll y = (c - x * a) / b;
if(x>=0)//看x大小要求而定
cout << x << ' ' << y << endl;
return 0;
