题意:有n元钱，有2种单价不同的商品，是否存在一种购买方式使得钱恰好花光，如果有输入任意一种方式，如果没有输出“NO”
题解：可以使用拓展欧几里得快速求解。
#include<iostream>
using namespace std;
#define ll long long
ll gcd(ll a, ll b)
{
return b? gcd(b, a%b) : a;
} void ex_gcd(ll a, ll b, ll &x, ll &y, ll &d)
{
if(!b)
{
x = , y = , d = a;
return ;
}
ex_gcd(b, a%b, y, x, d);
y -= a/b * x;
return ;
}
int main()
{
ll m, a, b, x, y;
cin >> m >> a >> b;
ll d = gcd(a, b);
if(m%d)
{
cout << "NO\n";
return ;
}
ex_gcd(a, b, x, y, d);
x *= m/d, y *= m/d;
a /= d, b /= d;
if(x< && y <)
{
cout << "NO\n";
}
else if(x < )
{
x = -x;
ll z;
if(x%b) z = x/b+; //找到最小的正数x
else z = x/b;
x = -x + z * b;
y = y - z*a;
if(y < )
cout << "NO\n";
else cout << "YES\n" << x << ' ' << y << endl;
}
else if(y < )
{
y = -y;
ll z;
if(y%a) z = y/a+;
else z = y/a;
y = -y + z*a;
x = x - z*b;
if(x < )
cout << "NO\n";
else cout << "YES\n" << x << ' ' << y << endl;
}
else
cout << "YES\n" << x << ' ' << y << endl;
return ;
}