P1298题解

xwh_hh · 2023-01-04 14:13:56 · 题解

终于 AC 一道紫题了，发个题解纪念一下。
现提供一种 O(m) 的思路。
先来讲一个简单的东西：

所以只要知道分母，分子可以 O(1) 求出。

Q: 数据怎么处理？
A: 可以用分数处理，降低误差。
Q: 约分耗时间怎么办？
A: 不要约。
Q: 分子分母在运算时爆 long long 怎么办？
A: 用 __int128 就行。
Q: 输出怎么处理？
A: 强转 int 或 long long。
Q: 怎么实现？
A: 分数用结构体，具体上代码（仅供参考，不要抄）：

#include<bits/stdc++.h>
using namespace std;
struct num{//分数
    __int128 son,mum;
    num(){}
    num(__int128 a,__int128 b){
        son=a,mum=b;
    }
  //重载运算符，方便后面计算。
  //加减法公分母为两个分母之积、
    num operator+(const num &k)const{
        num ans;
        ans.son=son*k.mum+k.son*mum;
        ans.mum=mum*k.mum;
        return ans;
    }
    num operator-(const num &k)const{
        num ans;
        ans.son=son*k.mum-k.son*mum;
        ans.mum=mum*k.mum;
        return ans;
    }
    num operator*(const num &k)const{
        num ans;
        ans.son=son*k.son;
        ans.mum=mum*k.mum;
        return ans;
    }
  //十字交叉法
    bool operator>(const num &k)const{
        return son*k.mum>mum*k.son;
    }
    bool operator==(const num &k)const{
        return son*k.mum==mum*k.son;
    }
    bool operator<(const num &k)const{
        return son*k.mum<mum*k.son;
    }
}; 
__int128 flr(num h){//向下取整
    return h.son/h.mum;
}
__int128 cel(num h){//向上取整
    return (h.son+h.mum-1)/h.mum;
}
num ans;
num key;
int n,m;
bool flag;
num error=num(1000000007,1);//误差，初始化为正无穷。
void Judge(num k,bool gk){//尝试优化  gk==0说明k偏小，否则k偏大
    if(k==ans) return;
    num a;
    if(gk) a=k-key;
    else a=key-k;
    if(a>error) return;
    if(a==error) flag=1;
    if(a<error){
        flag=0;
        ans=k;
        error=a;
    }
}
num read_a_num(){//读入小数，转为分数
    double tmp;
    cin>>tmp;
    tmp*=10000000000;
    return num(floor(tmp+0.01),10000000000);
}
int main(){
    cin>>n>>m;
    key=read_a_num();
    ans=num(1,1);
    for(int mum=1;mum<=m;mum++){//枚举分母
        __int128 get1=flr(key*num(mum,1)),get2=cel(key*num(mum,1));
        if(get1>n) break;
        if(get2<=n)
            Judge(num(get2,mum),1);
        Judge(num(get1,mum),0);
    }
    if(flag) cout<<"TOO MANY";
    else{
        cout<<(long long)(ans.son)<<"/"<<(long long)(ans.mum);
    }
    return 0;
}

这题卡常数，最慢的点跑了 927ms。