icontofig | 发布于 2019-09-12 00:20:26 | 阅读量 368 | 二分
发布于 2019-09-12 00:20:26 | 二分

题目大意

求一个分数x,使得其分母不超过100000并且f(x)与g(x)在x处最接近。

题解

首先很明确这是个二分的题目,不过分数怎么二分……。

首先我们二分出x3>k2的最小的整数x,然后这样进行分数二分:

首先设左端点分子为lz = x-1,分母为lm = 1,右端点分子为rz = x,分母为rm = 1.

二分的时候,我们取分子midz = lz + rz,分母midm = lm + rm。

判断是否小于当前差值最小值,如果是记录此时答案。

然后判断当前分数的三次方是否比k2大,如果是,区间右端点左移,否则区间左端点右移。

当分母midm > 100000的时候终止二分,输出答案即可。

代码

#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;
}



内容更新于: 2019-09-12 00:20:27
链接地址: http://blog.leanote.com/post/icontofig/HDU-6209-The-Intersection-%E4%BA%8C%E5%88%86

上一篇: The Preliminary Contest for ICPC Asia Shanghai 2019 C.Triple FFT + 生成函数

下一篇: The Preliminary Contest for ICPC Asia Xuzhou 2019 G.Colorful String PAM(回文自动机) + 可持久化线段树

368 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航