Gym 102443 #Codeforces

Gym 102443C.cpp

#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define debug(s, r) std::cerr << #s << ": " << (s) << (r == 0 ? ' ' : '\n')
#define pii pair<int, int>
#define sqr(x) ((x) * (x))

using namespace std;

ll bin_search(ll l, ll r, std::function<bool(ll)> check) {
    ll result = l, mid;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (check(mid)) {
            result = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return result;
}

void solve() {
    ll L, len, mx, a, b, c, n;
    cin >> L >> len;
    len = len - L + 1;
    mx = bin_search(3, 2000, [&](ll mid) -> bool {
        return mid * mid * mid * (mid - 2) >= L;
    });
    L -= (mx - 1) * (mx - 1) * (mx - 1) * (mx - 3);

    a = (ll)ceil(1.0 * L / (mx * mx * (mx - 2) - (mx - 1) * (mx - 1) * (mx - 3)));
    a = min(a, mx); // 如果a应该为mx，那么通过上式求得的a可能大于mx
    L -= (a - 1) * (mx * mx * (mx - 2) - (mx - 1) * (mx - 1) * (mx - 3));

    if (a == mx) {
        // b = bin_search(1, mx, [&](ll mid) -> bool {
        //     if(mid == mx) return true;
        //     return mid * mx * (mx - 2) >= L;
        // });
        b = ceil(1.0 * L / (mx * (mx-2)));
        b = min(b, mx);
        L -= (b - 1) * mx * (mx - 2);
    } else {
        b = bin_search(1, mx, [&](ll mid) -> bool {
            if(mid == mx) return true;
            return mid * (mx * (mx - 2) - (mx - 1) * (mx - 3)) >= L;
        });
        // b = ceil(1.0 * L / (mx * (mx - 2) - (mx - 1) * (mx - 3)));
        // b = min(b, mx);
        L -= (b - 1) * (mx * (mx - 2) - (mx - 1) * (mx - 3));
    }

    if(a == mx || b == mx){
        c = ceil(1.0 * L / (mx-2));
        c = min(c, mx);
        L -= (c-1) * (mx-2);
    }else{
        c = min(L, mx);
        L -= c-1;
    }

    if(a == mx || b == mx || c == mx){
        n = L + 2;
    }else{
        n = mx;
    }
    // debug(a, 0), debug(b, 0), debug(c, 0), debug(n, 1);
    for(int i=0; i<len; i++){
        double val_a = pow(1.0 * a / c, n);
        double val_b = pow(1.0 * b / c, n);
        // 判断条件必须是 '<'，精度（数据）问题
        // 正解应当是：如果fabs(val_a+val_b-1) < eps，则暴力高精度计算
        if(val_a + val_b < 1){ 
            printf("%lld^%lld+%lld^%lld<%lld^%lld\n", a, n, b, n, c, n);
        }else{
            printf("%lld^%lld+%lld^%lld>%lld^%lld\n", a, n, b, n, c, n);
        }
        if(a == mx && b == mx && c == mx && n == mx){
            mx++;
            a = b = c = 1;
            n = mx;
        }else{
            if(n < mx){
                n++;
            }else{
                c++;
                if(c > mx) c=1, b++;
                if(b > mx) b=1, a++;
                n = (c==mx||b==mx||a==mx)?3:mx;
            }
        }
    }
}

signed main() {
    Android;
    solve();
}