Solution for Live Archive 6428 - A+B Using Big Integer

/*
 * 6428.cpp
 *
 *  Created on: Sep 3, 2014
 *      Author: ghooo
 */

#include <cstring>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <vector>
#include <set>
#include <complex>
#include <list>
#include <climits>
#include <cctype>
#include <bitset>
//#include <windows.h>

using namespace std;

#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define sz(v) ((ll)v.size())
#define rep(i,m) for(int i=0;i<(int)(m);++i)
#define repe(i,n,m) for(int i=n;i<=(int)(m);++i)
#define rep2(i,n,m) for(int i=n;i<(int)(m);i++)
#define For(it,c) for(__typeof(c.begin()) it=c.begin();it!=c.end();++it)
#define reset(a,b) memset(a,b,sizeof(a))
#define mp make_pair
#define dot(a,b) ((conj(a)*(b)).X)
#define X real()
#define Y imag()
#define length(V) (hypot((V).X,(V).Y))
#define vect(a,b) ((b)-(a))
#define cross(a,b) ((conj(a)*(b)).imag())
#define normalize(v) ((v)/length(v))
#define rotate(p,about,theta) ((p-about)*exp(point(0,theta))+about)
#define pointEqu(a,b) (comp(a.X,b.X)==0 && comp(a.Y,b.Y)==0)
#define clrq(x) while(!x.empty()) x.pop();
#define clrvv(v) rep(i,sz(v))v[i].clear();
#define PRINT false
#define debug(x) if(PRINT)cerr << #x << ": " << x << endl;
#define debugv(v) cerr << #v << ": ";For(it,v)cerr <<(*it)<<", "; cerr<<endl;

typedef stringstream ss;
//typedef long long ll;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<string> vs;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<vector<int> > vii;
typedef long double ld;
typedef complex<double> point;
typedef pair<point, point> segment;
typedef pair<double, point> circle;
typedef vector<point> polygon;
typedef unsigned long long ull;
//typedef long long ll;

//==============================================================
// handling triples
#define tfirst first
#define tsecond second.first
#define tthird second.second
#define mt(x,y,z) mp(x,mp(y,z))
//---------------------------------------------------------------

const int oo = (int) 1e9;
const double PI = 2 * acos(0.0);
const double eps = 1e-9;
// base and base_digits must be consistent
const int base = 1000000000;
const int base_digits = 9;

struct bigint {
 vector<int> a;
 int sign;

 bigint() :
   sign(1) {
 }

 bigint(long long v) {
  *this = v;
 }

 bigint(const string &s) {
  read(s);
 }

 void operator=(const bigint &v) {
  sign = v.sign;
  a = v.a;
 }

 void operator=(long long v) {
  sign = 1;
  if (v < 0)
   sign = -1, v = -v;
  for (; v > 0; v = v / base)
   a.push_back(v % base);
 }

 bigint operator+(const bigint &v) const {
  if (sign == v.sign) {
   bigint res = v;

   for (int i = 0, carry = 0;
     i < (int) max(a.size(), v.a.size()) || carry; ++i) {
    if (i == (int) res.a.size())
     res.a.push_back(0);
    res.a[i] += carry + (i < (int) a.size() ? a[i] : 0);
    carry = res.a[i] >= base;
    if (carry)
     res.a[i] -= base;
   }
   return res;
  }
  return *this - (-v);
 }

 bigint operator-(const bigint &v) const {
  if (sign == v.sign) {
   if (abs() >= v.abs()) {
    bigint res = *this;
    for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {
     res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
     carry = res.a[i] < 0;
     if (carry)
      res.a[i] += base;
    }
    res.trim();
    return res;
   }
   return -(v - *this);
  }
  return *this + (-v);
 }

 void operator*=(int v) {
  if (v < 0)
   sign = -sign, v = -v;
  for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) {
   if (i == (int) a.size())
    a.push_back(0);
   long long cur = a[i] * (long long) v + carry;
   carry = (int) (cur / base);
   a[i] = (int) (cur % base);
   //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
  }
  trim();
 }

 bigint operator*(int v) const {
  bigint res = *this;
  res *= v;
  return res;
 }

 friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) {
  int norm = base / (b1.a.back() + 1);
  bigint a = a1.abs() * norm;
  bigint b = b1.abs() * norm;
  bigint q, r;
  q.a.resize(a.a.size());

  for (int i = a.a.size() - 1; i >= 0; i--) {
   r *= base;
   r += a.a[i];
   int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
   int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
   int d = ((long long) base * s1 + s2) / b.a.back();
   r -= b * d;
   while (r < 0)
    r += b, --d;
   q.a[i] = d;
  }

  q.sign = a1.sign * b1.sign;
  r.sign = a1.sign;
  q.trim();
  r.trim();
  return make_pair(q, r / norm);
 }

 bigint operator/(const bigint &v) const {
  return divmod(*this, v).first;
 }

 bigint operator%(const bigint &v) const {
  return divmod(*this, v).second;
 }

 void operator/=(int v) {
  if (v < 0)
   sign = -sign, v = -v;
  for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) {
   long long cur = a[i] + rem * (long long) base;
   a[i] = (int) (cur / v);
   rem = (int) (cur % v);
  }
  trim();
 }

 bigint operator/(int v) const {
  bigint res = *this;
  res /= v;
  return res;
 }

 int operator%(int v) const {
  if (v < 0)
   v = -v;
  int m = 0;
  for (int i = a.size() - 1; i >= 0; --i)
   m = (a[i] + m * (long long) base) % v;
  return m * sign;
 }

 void operator+=(const bigint &v) {
  *this = *this + v;
 }
 void operator-=(const bigint &v) {
  *this = *this - v;
 }
 void operator*=(const bigint &v) {
  *this = *this * v;
 }
 void operator/=(const bigint &v) {
  *this = *this / v;
 }

 bool operator<(const bigint &v) const {
  if (sign != v.sign)
   return sign < v.sign;
  if (a.size() != v.a.size())
   return a.size() * sign < v.a.size() * v.sign;
  for (int i = a.size() - 1; i >= 0; i--)
   if (a[i] != v.a[i])
    return a[i] * sign < v.a[i] * sign;
  return false;
 }

 bool operator>(const bigint &v) const {
  return v < *this;
 }
 bool operator<=(const bigint &v) const {
  return !(v < *this);
 }
 bool operator>=(const bigint &v) const {
  return !(*this < v);
 }
 bool operator==(const bigint &v) const {
  return !(*this < v) && !(v < *this);
 }
 bool operator!=(const bigint &v) const {
  return *this < v || v < *this;
 }

 void trim() {
  while (!a.empty() && !a.back())
   a.pop_back();
  if (a.empty())
   sign = 1;
 }

 bool isZero() const {
  return a.empty() || (a.size() == 1 && !a[0]);
 }

 bigint operator-() const {
  bigint res = *this;
  res.sign = -sign;
  return res;
 }

 bigint abs() const {
  bigint res = *this;
  res.sign *= res.sign;
  return res;
 }

 long long longValue() const {
  long long res = 0;
  for (int i = a.size() - 1; i >= 0; i--)
   res = res * base + a[i];
  return res * sign;
 }

 friend bigint gcd(const bigint &a, const bigint &b) {
  return b.isZero() ? a : gcd(b, a % b);
 }
 friend bigint lcm(const bigint &a, const bigint &b) {
  return a / gcd(a, b) * b;
 }

 void read(const string &s) {
  sign = 1;
  a.clear();
  int pos = 0;
  while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
   if (s[pos] == '-')
    sign = -sign;
   ++pos;
  }
  for (int i = s.size() - 1; i >= pos; i -= base_digits) {
   int x = 0;
   for (int j = max(pos, i - base_digits + 1); j <= i; j++)
    x = x * 10 + s[j] - '0';
   a.push_back(x);
  }
  trim();
 }

 friend istream& operator>>(istream &stream, bigint &v) {
  string s;
  stream >> s;
  v.read(s);
  return stream;
 }

 friend ostream& operator<<(ostream &stream, const bigint &v) {
  if (v.sign == -1)
   stream << '-';
  stream << (v.a.empty() ? 0 : v.a.back());
  for (int i = (int) v.a.size() - 2; i >= 0; --i)
   stream << setw(base_digits) << setfill('0') << v.a[i];
  return stream;
 }

 static vector<int> convert_base(const vector<int> &a, int old_digits,
   int new_digits) {
  vector<long long> p(max(old_digits, new_digits) + 1);
  p[0] = 1;
  for (int i = 1; i < (int) p.size(); i++)
   p[i] = p[i - 1] * 10;
  vector<int> res;
  long long cur = 0;
  int cur_digits = 0;
  for (int i = 0; i < (int) a.size(); i++) {
   cur += a[i] * p[cur_digits];
   cur_digits += old_digits;
   while (cur_digits >= new_digits) {
    res.push_back(int(cur % p[new_digits]));
    cur /= p[new_digits];
    cur_digits -= new_digits;
   }
  }
  res.push_back((int) cur);
  while (!res.empty() && !res.back())
   res.pop_back();
  return res;
 }

 typedef vector<long long> vll;

 static vll karatsubaMultiply(const vll &a, const vll &b) {
  int n = a.size();
  vll res(n + n);
  if (n <= 32) {
   for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
     res[i + j] += a[i] * b[j];
   return res;
  }

  int k = n >> 1;
  vll a1(a.begin(), a.begin() + k);
  vll a2(a.begin() + k, a.end());
  vll b1(b.begin(), b.begin() + k);
  vll b2(b.begin() + k, b.end());

  vll a1b1 = karatsubaMultiply(a1, b1);
  vll a2b2 = karatsubaMultiply(a2, b2);

  for (int i = 0; i < k; i++)
   a2[i] += a1[i];
  for (int i = 0; i < k; i++)
   b2[i] += b1[i];

  vll r = karatsubaMultiply(a2, b2);
  for (int i = 0; i < (int) a1b1.size(); i++)
   r[i] -= a1b1[i];
  for (int i = 0; i < (int) a2b2.size(); i++)
   r[i] -= a2b2[i];

  for (int i = 0; i < (int) r.size(); i++)
   res[i + k] += r[i];
  for (int i = 0; i < (int) a1b1.size(); i++)
   res[i] += a1b1[i];
  for (int i = 0; i < (int) a2b2.size(); i++)
   res[i + n] += a2b2[i];
  return res;
 }

 bigint operator*(const bigint &v) const {
  vector<int> a6 = convert_base(this->a, base_digits, 6);
  vector<int> b6 = convert_base(v.a, base_digits, 6);
  vll a(a6.begin(), a6.end());
  vll b(b6.begin(), b6.end());
  while (a.size() < b.size())
   a.push_back(0);
  while (b.size() < a.size())
   b.push_back(0);
  while (a.size() & (a.size() - 1))
   a.push_back(0), b.push_back(0);
  vll c = karatsubaMultiply(a, b);
  bigint res;
  res.sign = sign * v.sign;
  for (int i = 0, carry = 0; i < (int) c.size(); i++) {
   long long cur = c[i] + carry;
   res.a.push_back((int) (cur % 1000000));
   carry = (int) (cur / 1000000);
  }
  res.a = convert_base(res.a, 6, base_digits);
  res.trim();
  return res;
 }
};
typedef bigint ll;

ll eGCD(ll a, ll b, ll &x, ll &y) {
 x = 1;
 y = 0;
 ll nx = 0, ny = 1;
 ll t, r;
 while (!b.isZero()) {
  r = a / b;
  t = a - r * b;
  a = b;
  b = t;
  t = x - r * nx;
  x = nx;
  nx = t;
  t = y - r * ny;
  y = ny;
  ny = t;
 }
 return a;
}
//ax+by=c
bool solveLDE(ll a, ll b, ll c, ll &x, ll &y, ll &g) {
 g = eGCD(a, b, x, y);
 x *= c / g;
 y *= c / g;
 return (c % g) == 0;
}

//(a*mi)%m=1
ll modInv(ll a, ll m) {
 ll mi, r;
 eGCD(a, m, mi, r);
 return (mi + m) % m;
}
bigint abs(bigint a) {
 a.sign = 1;
 return a;
}
//(a*x)%b=c
bool solve(ll a, ll b, ll c, ll &x) {
 ll y, g;
 if (solveLDE(a, b, c, x, y, g) && a * x + b * y == c) {
  if (x < 0) {
   x += (abs(x) / b) * b;
   if (x < 0)
    x += b;
  }
  return 1;
 }
 return 0;
}
int main() {

 ll a, b, s;
 while (cin >> a >> b >> s) {
  ll g = __gcd(a, b);
  if (s == a) {
   cout << "YES" << endl;
  } else if (s == b) {
   cout << "YES" << endl;
  } else if (g == 0 || !(s % g).isZero()) {
   cout << "NO" << endl;
  } else {
   a /= g, b /= g, s /= g;
   ll x, y;
   eGCD(a, b, x, y);
   x *= s;
   y *= s;

   bool toIncX = false;
   if (x < y)
    toIncX = true;

   if (x < 0) {
    ll incX = (abs(x) + b - 1) / b;
    x += incX * b;
    y -= incX * a;
   } else if (y < 0) {
    ll incY = (abs(y) + a - 1) / a;
    y += incY * a;
    x -= incY * b;
   }
   if (toIncX)
    a *= -1;
   else
    b *= -1;

   bool f = false;
   int trials = 50; // Increase the number of trials if you get wrong answer
   while (trials && !f && x >= 0 && y >= 0) {
    f = (__gcd(x, y) == 1);
    trials--;
    x += b;
    y += a;
   }
   if (f) {
    cout << "YES" << endl;

   } else {
    cout << "NO" << endl;
   }
  }
 }
 return 0;
}