結果

問題 No.3307 Almost Equal
ユーザー Kude
提出日時 2025-10-05 16:21:08
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,417 bytes
コンパイル時間 3,058 ms
コンパイル使用メモリ 297,964 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-05 16:21:28
合計ジャッジ時間 4,454 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:25:19: warning: ‘__int128 unsigned {anonymous}::floor_sum_unsigned(__int128 unsigned, __int128 unsigned, __int128 unsigned, __int128 unsigned)’ defined but not used [-Wunused-function]
   25 | unsigned __int128 floor_sum_unsigned(unsigned __int128 n,
      |                   ^~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;


// @param n `n < 2^32`
// @param m `1 <= m < 2^32`
// @return sum_{i=0}^{n-1} floor((ai + b) / m) (mod 2^64)
unsigned __int128 floor_sum_unsigned(unsigned __int128 n,
                                      unsigned __int128 m,
                                      unsigned __int128 a,
                                      unsigned __int128 b) {
    unsigned __int128 ans = 0;
    while (true) {
        if (a >= m) {
            ans += n * (n - 1) / 2 * (a / m);
            a %= m;
        }
        if (b >= m) {
            ans += n * (b / m);
            b %= m;
        }

        unsigned __int128 y_max = a * n + b;
        if (y_max < m) break;
        // y_max < m * (n + 1)
        // floor(y_max / m) <= n
        n = (unsigned __int128)(y_max / m);
        b = (unsigned __int128)(y_max % m);
        std::swap(m, a);
    }
    return ans;
}


__int128 my_floor_sum(__int128 n, __int128 m, __int128 a, __int128 b) {
    // assert(0 <= n && n < (1LL << 32));
    // assert(1 <= m && m < (1LL << 32));
    unsigned __int128 ans = 0;
    if (a < 0) {
        unsigned __int128 a2 = internal::safe_mod(a, m);
        ans -= 1ULL * n * (n - 1) / 2 * ((a2 - a) / m);
        a = a2;
    }
    if (b < 0) {
        unsigned __int128 b2 = internal::safe_mod(b, m);
        ans -= 1ULL * n * ((b2 - b) / m);
        b = b2;
    }
    return ans + internal::floor_sum_unsigned(n, m, a, b);
}


auto floor_div(signed_integral auto x, signed_integral auto y) {
  return x / y - ((x ^ y) < 0 && x % y != 0);
}
template <integral T>
T floor_div(T x, unsigned_integral auto y) {
  return x >= 0 ? T(x / y) : -T(-x / y + (-x % y != 0));
}
auto ceil_div(signed_integral auto x, signed_integral auto y) {
  return x / y + ((x ^ y) >= 0 && x % y != 0);
}
template <integral T>
T ceil_div(T x, unsigned_integral auto y) {
  return x >= 0 ? T(x / y + (x % y != 0)) : -T(-x / y);
}

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll a, b, c, d;
  cin >> a >> b >> c >> d;
  if (a*d < b*c) swap(a, c), swap(b, d);
  if (a*d == b*c) {
    cout << -1 << '\n';
    return 0;
  }
  ll ans = 0;
  {
    // iA/B<1/2
    // i<B/2A
    ans += ceil_div(b, 2*a);
    ans--;  // i = 0
  }
  // i(a/b-c/d) < 1
  // i<bd/(ad-bc)
  ll imx = ceil_div(b*d, a*d-b*c) - 1;
  assert(imx >= 0);
  // floor(imx*c/d+1/2)
  auto kmx = (2*__int128(imx)*c+d) / (2 * d);
  // 1 <= k <= kmx
  // k<=i*c/d+1/2
  // (k-1/2)d/c = (2k-1)d/2c <= i
  // i < (2k+1)b/2a
  // floor( (2dk - d + 2c - 1) / 2c)
  // floor( (2bk + b + 2a - 1) / 2a)
  // 1 <= k <= kmx
  auto r1 = my_floor_sum(kmx, 2*a, 2*b, 2*b+b+2*a-1);
  auto r2 = my_floor_sum(kmx, 2*c, 2*d, 2*d-d+2*c-1);
  cout << ll((r1 - r2) + ans) << '\n';
}
0