10分求助!
查看原帖
10分求助!
945845
Chernobog_Belobog楼主2024/3/4 21:12

只用了二分,样例过了,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;
}
2024/3/4 21:12
加载中...