2021.9.3 阿里笔试AK贴

题目

　　给定三个正整数a, b, c 请找到满足下面条件的x,y的组数

　　1, a <= x^2 <=b　　

       2, a <= y^3 <= b

      3, |x^2 - y^3| <= c

其中

1 <= a <= b <= 1e18

0 <= c <= 1e18

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL maxnum = 1e18;
LL a, b, c;
LL get_2(LL x) {
    LL l = 1, r = 1e9;
    while(l<r) {
        LL mid = (l+r) / 2;
        if(mid * mid < x)
            l = mid + 1;
        else r = mid;
    }
    return l;
}

LL get_3(LL x) {
    LL l = 1, r = 1e6;
    while(l<r) {
        LL mid = (l+r) / 2;
        if(mid * mid * mid < x)
            l = mid + 1;
        else r = mid;
    }
    return l;
}

int main()
{
    cin >> a >> b >> c;
    LL x1 = get_2(a);
    LL x2 = get_2(b);
    if(x2 * x2 > b) x2 --;

    LL y1 = get_3(a);
    LL y2 = get_3(b);
    if(y2 * y2 * y2 > b) y2 --;

    // printf("x: %lld %lld
", x1, x2);
    // printf("y: %lld %lld
", y1, y2);

    LL ans = 0;
    for(LL y = y1; y<=y2; y++) {
        LL k1 = max(y * y * y - c, 0LL);
        LL k2 = y * y * y + c;
        if(y * y * y >= maxnum - c)  k2 = maxnum;

        LL t1 = get_2(k1);
        LL t2 = get_2(k2);
        if(t2 * t2 > k2) t2--;

        // printf("t: %lld %lld
", t1, t2);
        if(t2<x1 || t1>x2) continue;
        else {
            t1 = max(t1, x1);
            t2 = min(t2, x2);
            ans += (t2 - t1 + 1);
        }
    }
    cout << ans << endl;
    return 0;
}