只用了二分,样例过了,cclt是用来算在横坐标x之前,两条函数之间的整点个数(可能有些抽象
#include <bits/stdc++.h>
using namespace std;
#define int long long
long long a , b , c , d , ans;
int cclt(int x) {
int ux , dx;
if (x % b != 0) ux = (x - x % b) + b;
else ux = x;
if (x % d != 0) dx = (x - x % d) + d;
else dx = x;
int uy = ux / b * a , dy = dx / d * c;
int k1 = __gcd(ux , uy) , k2 = __gcd(dx , dy);
int x1 = ux / k1 , y1 = uy / k1 , x2 = dx / k2 , y2 = dy / k2;
int big = (k1 * x1 * y1 - x1 + y1 - 1) * 1.0 / 2 * k1;
int small = (k2 * x2 * y2 - x2 + y2 + 1) * 1.0 / 2 * k2;
// cout << x << " " << ux << " " << uy << " " << dx << " " << dy << " ";
int preuh = (x - x % b) / b * a , uh = x * a / b , mb = 0;
int predh = (x - x % d) / d * c , dh = x * c / d , ms = 0;
// cout << preuh << " " << uh << " " << predh << " " << dh << " " << big << " " << small << " ";
if (preuh == uh && ux != x) {
mb += (uh + 1 + uy) * (uy - uh) / 2;
int p = ux - uy + uh;
mb += (p - x) * uh;
mb--;
} else if (ux != x) {
mb += (uh + 1 + uy) * (uy - uh) / 2;
mb--;
} if (predh == dh && dx != x) {
ms += (dh + 1 + dy) * (dy - dh) / 2;
int p = dx - dy + dh;
ms += (p - x) * dh;
} else if (dx != x) {
ms += (dh + 1 + dy) * (dy - dh) / 2;
}
big -= mb , small -= ms;
// cout << mb << " " << ms << " " << big << " " << small << endl;
return big - small;
}
bool check(int x) {
int s = cclt(x);
return s >= 1;
}
signed main() {
while (cin >> a >> b >> c >> d) {
int ab = __gcd(a , b) , cd = __gcd(c , d);
a /= ab , b /= ab , c /= cd , d /= cd;
if (b * c > a * d) swap(a , c) , swap(b , d);
int l = 1 , r = 5000; ans = 0;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid)) ans = mid , r = mid - 1;
else l = mid + 1;
}
cout << c * ans / d + 1 << "/" << ans << endl;
}
return 0;
}