提出 #493719

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) ((int)(a).size())
#define eb emplace_back

#define endl '\n'

typedef long long ll;
typedef pair<int, int> PI;


// ax + by == 1
ll extgcd(ll a, ll b, ll &x, ll &y){
  ll d = a;
  if(b != 0) {
    d = extgcd(b, a % b, y, x);
    y -= (a / b) * x;
  } else {
    x = 1;
    y = 0;
  }
  return d;
}


void solve(){
  ll a, b, c;
  cin >> a >> b >> c;
  if(a == c || b == c){
    cout << 1 << endl;
    return;
  }
  
  
  if(c > a && c > b){
    cout << -1 << endl;
    return;
  }

  ll g = __gcd(a, b);
  if(c % g != 0){
    cout << -1 << endl;
    return;
  }
  a /= g;
  b /= g;
  c /= g;
  ll x, y;
  ll ans = 1LL << 60LL;

  rep(i, 2){
    swap(a, b);
    // if(c > a) continue;
    rep(j, 2){
      if(j && a < c) continue;
      if(!j && b < c) continue;
      extgcd(a, b, x, y);
      y = -y;
      // assert(a * x - b * y == 1);
      // cout << i << " " << j << " " << a << " " << b << endl;
      // cout << x << " " << y << endl;
      if(j){
        x *= c - a;
        y *= c - a;
      }else{
        x *= c;
        y *= c;
      }
      
      // seiji

      rep(i, 30){
        if(x < 0 || y < 0){
          x += b << (ll)i;
          y += a << (ll)i;
        }
      }
      
      for(ll i = 30; i >= 0; --i){
        if(x - (b << i) >= 0 && y - (a << i) >= 0){
          x -= b << i;
          y -= a << i;
        }
      }
      
      
      //cout << "aft sub " << x << " " << y << endl;
      ans = min(ans, x * 2 + y * 2);
      // cout << "ans " << ans << endl;
    }
  }
  
  cout << ans << endl;
  // exit(0);
}

int main(int argc, char *argv[])
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  int t;
  cin >> t;
  rep(i, t) solve();
  
  return 0;
}

提出情報

ジャッジ結果