結果

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

ソースコード

diff # 

#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;

// https://drken1215.hatenablog.com/entry/2022/12/14/235718
template <typename T>
T floor_sum(T n, T m, T a, T b) {
	if (n == 0) return 0;
	T res = 0;
	if (a >= m) {
		res += n * (n - 1) * (a / m) / 2;
		a %= m;
	}
	if (b >= m) {
		res += n * (b / m);
		b %= m;
	}
	if (a == 0) return res;
	T ymax = (a * n + b) / m, xmax = ymax * m - b;
	if (ymax == 0) return res;
	res += (n - (xmax + a - 1) / a) * ymax;
	res += floor_sum(ymax, a, m, (a - xmax % a) % a);
	return res;
}
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 = floor_sum<i128>(mx - 1, 2 * c, 2 * d, 3 * d + 2 * c - 1);
	auto t2 = floor_sum<i128>(mx - 1, 2 * a, 2 * b, b + 2 * a - 1);
	ll ans = (t1 - t2);
	ans += (d + 2 * c - 1) / (2 * c) - 1;
	cout << ans << '\n';
}

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