526互联

AtCoder Regular Contest 123 E Training

发布时间 2023-04-28 17:39:39作者: zltzlt

洛谷传送门

AtCoder 传送门

不妨假设 \(B_X \le B_Y\)。设 \(f(x) = A_X + \frac{x}{B_X}, g(x) = A_Y + \frac{x}{B_Y}, F(x) = \left\lfloor{f(x)}\right\rfloor, G(x) = \left\lfloor{g(x)}\right\rfloor\)，题目即求 \(\sum\limits_{x=1}^n [F(x) = G(x)]\)。

我一开始尝试化简式子，然后发现不能合并两个下取整的分数。

然后尝试二分 \(F(x) - G(x) = 0\) 的区间，很快也发现不行，因为 \(F(x) - G(x)\) 不单调，有可能出现 \(0,1,0,1\) 反复横跳的情况。

其实与其考虑 \(F(x) - G(x)\)，不如先考虑 \(f(x) - g(x)\)，它是斜率 \(\ge 0\) 的一次函数。我们发现：

  • \(f(x) - g(x) \in (-1,0], F(x) - G(x) \in \{-1,0\}\)；
  • \(f(x) - g(x) \in (0,1], F(x) - G(x) \in \{0,1\}\)。

而满足 \(f(x) - g(x) \in (-1,0]\) 和 \(f(x) - g(x) \in (0,1]\) 的区间可以二分得到。接下来以第一种情况为例（第二种情况是对称的），考虑如何计算。

现在问题仍然是求 \(\sum\limits_{x=l}^r [F(x) - G(x) = 0]\)，但是 \(F(x) - G(x) \in \{-1,0\}\)。考虑计算 \(\sum\limits_{x=l}^r F(x) - G(x)\)，设结果为 \(k\)，发现 \(\sum\limits_{x=l}^r [F(x) - G(x) = -1] = -k\)，这样 \(\sum\limits_{x=l}^r [F(x) - G(x) = 0] = r - l + 1 + k\)，就把区间里求多少数的值等于某个数的问题转化成了区间求和。

接下来问题变成了求 \(\sum\limits_{x=l}^r F(x) - G(x) = (\sum\limits_{x=l}^r A_X + \left\lfloor\frac{i}{B_X}\right\rfloor) - (\sum\limits_{x=l}^r A_Y + \left\lfloor\frac{i}{B_Y}\right\rfloor)\)。这个就爱怎么做怎么做了，虽然你闲得蛋疼也可以类欧（

code 
// Problem: E - Training
// Contest: AtCoder - AtCoder Regular Contest 123
// URL: https://atcoder.jp/contests/arc123/tasks/arc123_e
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

ll dfs(ll a, ll b, ll c, ll n) {
	if (!a || !n) {
		return (n + 1) * (b / c);
	}
	if (n < 0) {
		return 0;
	}
	if (a >= c || b >= c) {
		return dfs(a % c, b % c, c, n) + (a / c) * (n * (n + 1) / 2) + (b / c) * (n + 1);
	}
	ll m = (a * n + b) / c;
	return m * n - dfs(c, c - b - 1, a, m - 1);
}

inline ll calc(ll a, ll b, ll c, ll l, ll r) {
	return dfs(a, b, c, r) - dfs(a, b, c, l - 1);
}

void solve() {
	ll n, a, b, c, d;
	scanf("%lld%lld%lld%lld%lld", &n, &a, &b, &c, &d);
	if (b > d) {
		swap(a, c);
		swap(b, d);
	}
	ll l = 1, r = n, p1 = -1, p2 = n + 1, p3 = -1;
	while (l <= r) {
		ll mid = (l + r) >> 1;
		if (mid * (d - b) > b * d * (c - a - 1)) {
			p1 = mid;
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	if (p1 == -1) {
		puts("0");
		return;
	}
	l = p1;
	r = n;
	while (l <= r) {
		ll mid = (l + r) >> 1;
		if (mid * (d - b) > b * d * (c - a)) {
			p2 = mid;
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	l = p2;
	r = n;
	while (l <= r) {
		ll mid = (l + r) >> 1;
		if (mid * (d - b) <= b * d * (c - a + 1)) {
			p3 = mid;
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	if (p3 == -1) {
		p3 = p2 - 1;
	}
	ll ans = 0, k = calc(1, c * d, d, p1, p2 - 1) - calc(1, a * b, b, p1, p2 - 1);
	ans += p2 - p1 - k;
	k = calc(1, a * b, b, p2, p3) - calc(1, c * d, d, p2, p3);
	ans += p3 - p2 + 1 - k;
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}