题目
给定三个正整数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\n", x1, x2); // printf("y: %lld %lld\n", 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\n", 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; }