扩展欧几里得应用1（数论~扯上数论就很高端的感觉~~）

【题意】
解不定方程Ax+By=K（得到的x和y只是其中一组解）
给出A、B、K，求出x和y，满足Ax+By=K。

【输入格式】
一行三个整数 A，B，K。 1 ≤ A，B，K ≤ 10^9 

【输出格式】
一行两个整数 x,y。如果无解，输出"no solution!"

【样例输入】
12 15  3

【样例输出】
-1 1

假设当前要求 gcd(a,b)，并求出了一组 x 和 y 使得 ax+by=GCD
已经求出 gcd(b,a%b) 并求出了一组 tx 和 ty 使得 b×tx+(a%b)×ty=GCDb×tx+(a%b)×ty=GCD
那么这两个相邻的状态之间是否存在某种关系呢？
ax+by=GCD=b×tx+(a%b)×ty
ax+by=b×tx+(a−⌊a/b⌋×b)×ty
ax+by=b×tx−⌊a/b⌋×b×ty+a×ty
ax+by=b×(tx−⌊a/b⌋×ty)+a×ty
所以 x=ty,y=tx−⌊a/b⌋×ty

通过上述推导的公式我们可以得到 ax + by = gcd(a , b)的 x 和 y 的值

由该代码实现：

LL ExEuclid(LL a , LL b , LL &x , LL &y)
{
	if(b == 0)
	{
		x = 1;y = 0;
		return a;
	}
	LL tx , ty;
	LL d = ExEuclid(b , a%b , tx , ty);
	x = ty;
	y = tx - (a/b)*ty;
	return d ;
}

那么现在我们求的是ax + by = K

要判断一个情况就是K是否能整除 gcd(a , b) 不能整除的话就是无答案了， 能整除的话 ， x的取值就是x * K/gcd(a , b).

带入到y里面就能求出y了

代码：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL ExEuclid(LL a , LL b , LL &x , LL &y)
{
	if(b == 0)
	{
		x = 1;y = 0;
		return a;
	}
	LL tx , ty;
	LL d = ExEuclid(b , a%b , tx , ty);
	x = ty;
	y = tx - (a/b)*ty;
	return d ;
}
int main()
{
	LL A , B , K , x , y;
	scanf("%lld %lld %lld" , &A , &B , &K);
	LL d = ExEuclid(A , B , x , y);
	if(K % d != 0)
	{
		printf("no solution!\n");
	}
	else
	{
		x = x * K / d ;
		y = (K - A * x) / B;
		printf("%lld %lld\n" , x , y);
	}
	return 0;
}