結果

問題 No.3307 Almost Equal
コンテスト
ユーザー cho435
提出日時 2025-10-09 15:34:41
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,549 bytes
コンパイル時間 3,831 ms
コンパイル使用メモリ 253,996 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-10-09 15:34:50
合計ジャッジ時間 6,297 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 RE * 1
other AC * 34 WA * 11 RE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define all(x) begin(x), end(x)

template <class T> bool chmin(T& x, T y) {
	return x > y ? (x = y, true) : false;
}
template <class T> bool chmax(T& x, T y) {
	return x < y ? (x = y, true) : false;
}

struct io_setup {
	io_setup() {
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout << fixed << setprecision(15);
	}
} io_setup;

template <typename T>
T sum_of_floor(T n, T m, T a, T b) {
	T ret = 0;
	if (a >= m) ret += (n - 1) * n * (a / m) / 2, a %= m;
	if (b >= m) ret += n * (b / m), b %= m;
	T y = (a * n + b) / m;
	if (y == 0) return ret;
	T x = y * m - b;
	ret += (n - (x + a - 1) / a) * y;
	ret += sum_of_floor<T>(y, a, m, (a - x % a) % a);
	return ret;
}
using i128 = __int128_t;

ll greedy(ll a, ll b, ll c, ll d) {
	ll res = 0;
	rep(i, 1, 10000) {
		ll x = (2 * a * i + b) / (2 * b);
		ll y = (2 * c * i + d) / (2 * d);
		if (x == y) {
			res++;
			cout << i << ' ' << x << endl;
		}
	}
	return res;
}

void solve() {
	ll a, b, c, d;
	cin >> a >> b >> c >> d;
	if (a * d == b * c) {
		cout << "-1\n";
		return;
	}
	if (a * d > b * c) {
		swap(a, c);
		swap(b, d);
	}
	ll dv = 2 * (b * c - a * d);
	ll mx = (b * c + a * d + dv - 1) / dv;
	auto t1 = sum_of_floor<i128>(mx, 2 * c, 2 * d, d + 2 * c - 1);
	auto t2 =
		sum_of_floor<i128>(mx, 2 * a, 2 * b, -b + 2 * a - 1) + b / (2 * a) + 1;
	cout << (ll)(t1 - t2) << '\n';
}

int main() {
	int t = 1;
	// cin >> t;
	while (t--) solve();
}
0