HDU 6209 The Intersection 分数二分

## 代码

```#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
double u,v;
ll lz,rz,lm,rm;
ll val,k;
int t;
ll mz,mm;
const long double INF = 1e19;
long double _abs(long double x){
return (x < 0) ? -x : x;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while(t--){
cin >> k;
val = 0;
ll l = 1,r = 1e5;
while(l <= r){
ll mid = (l + r) >> 1;
if(mid * mid * mid  >= k * k){
val = mid;
r = mid - 1;
}
else l = mid + 1;
}
if(val * val * val == k * k){
cout << val << "/1" << "\n";
continue;
}
lm = rm = 1;lz = val - 1;rz = val;
ll b = 0;
long double mn = INF;
ll A,B;
long double kp = k * k;
mm = 0,mz = 0;
while(true){
mz = lz + rz;
mm = lm + rm;
if(mm > 100000)break;
long double u = mz;
long double v = mm;
long double now = u * u * u / v / v / v;
if(_abs(now - kp) < mn){
mn = _abs(now - kp);
A = mz;B = mm;
}
if(now - kp > eps)
rz = mz,rm = mm;
else lz = mz,lm = mm;
}
ll g = __gcd(A,B);
A /= g;
B /= g;
cout << A << "/" << B << "\n";
}
return 0;
}```

0 条评论