*[hackerrank]Die Hard 3

https://www.hackerrank.com/contests/w7/challenges/die-hard-3

首先，发现c <= max(a, b) 而且 c = aX + bY时有解。然后根据扩展欧几里得算法知道c % gcd(a, b) == 0时有解。

#include <vector>
#include <iostream>using namespace std;int gcd(int a, int b) {
if (a % b == 0) {
return b;
} else {
return gcd(b, a % b);
}
}int main() {
int T;
cin >> T;
while (T--) {
int a, b, c;
cin >> a >> b >> c;
int r = gcd(a, b);
if (c % r == 0 && c <= max(a, b)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
    return 0;
}