AtCoder Beginner Contest 333 G

https://atcoder.jp/contests/abc333/tasks/abc333_g

分母がN以下で実数rに最も近い分数を最良近似と言います。これは連分数と結びついています。
例えば、0.45を連分数で表すと、

となります。これは次のように求められます。
の逆数を取るとで、この整数部分は2で、小数部分は、この逆数はで、整数部分は4で、小数部分は、この逆数は2なので、整数部分は2です。
この3つの整数部分、2, 4, 2を並べると連分数になります。
さて、この連分数を途中で打ち切ると、最良近似になります。計算してみると、となります。この計算は、整数部分を、とすると、


としたとき、が最良近似になります。
ただし、をとなるcで置き換えても最良近似になります。
Rustではi128があるので、これを使った分数構造体を作ればオーバーフローせずに計算できますね。

// Nearest Fraction
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}


//////////////////// process ////////////////////

#[derive(Clone, Copy)]
struct Fraction {
    num: i128,
    den: i128
}

use std::ops::{Add, Sub};

impl Add for Fraction {
    type Output = Self;
    
    fn add(self, other: Self) -> Self {
        let num = self.num * other.den + other.num * self.den;
        let den = self.den * other.den;
        Fraction::new(num, den)
    }
}

impl Sub for Fraction {
    type Output = Self;
    
    fn sub(self, other: Self) -> Self {
        let num = self.num * other.den - other.num * self.den;
        let den = self.den * other.den;
        Fraction::new(num, den)
    }
}

impl std::cmp::PartialOrd for Fraction {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        let num1 = self.num * other.den;
        let num2 = other.num * self.den;
        num1.partial_cmp(&num2)
    }
}

impl std::cmp::PartialEq for Fraction {
    fn eq(&self, other: &Self) -> bool {
        let num1 = self.num * other.den;
        let num2 = other.num * self.den;
        num1 == num2
    }
}


impl Fraction {
    fn new(num: i128, den: i128) -> Fraction {
        let d = Fraction::gcd(num, den);
        Fraction { num: num/d, den: den/d }
    }
    
    fn gcd(n: i128, m: i128) -> i128 {
        if m == 0 { n.abs() } else { Self::gcd(m, n % m) }
    }
    
    fn from_int(n: i128) -> Fraction {
        Fraction { num: n, den: 1 }
    }
    
    fn inverse(&self) -> Fraction {
        Fraction { num: self.den, den: self.num }
    }
}


//////////////////// process ////////////////////

fn read_input() -> (Fraction, i128) {
    let s: String = read();
    let s1 = &s[2..];
    let num: i128 = s1.parse().unwrap();
    let den: i128 = 10i128.pow(s1.len() as u32);
    let r = Fraction::new(num, den);
    let N: i128 = read();
    (r, N)
}

fn nearer(f1: Fraction, f2: Fraction, f: Fraction) -> Fraction {
    if f2 < f1 {
        nearer(f2, f1, f)
    }
    else if f <= f1 {
        // f <= f1 <= f2
        f1
    }
    else if f2 < f {
        // f1 <= f2 < f
        f2
    }
    else {
        // f1 < f <= f2
        let d1 = f - f1;
        let d2 = f2 - f;
        if d1 <= d2 { f1 } else { f2 }
    }
}

fn middle(f1: Fraction, f2: Fraction, c: i128) -> Fraction {
    let num = f1.num * c + f2.num;
    let den = f1.den * c + f2.den;
    Fraction::new(num, den)
}

fn nearest_fraction(r: Fraction, N: i128, r1: Fraction,
                    f1: Fraction, f2: Fraction) -> Fraction {
    let r2 = r1.inverse();
    let c = r2.num / r2.den;
    let f3 = middle(f2, f1, c);
    if f3.den >= N {
        let c1 = (N - f1.den) / f2.den;
        let f = middle(f2, f1, c1);
        nearer(f, f2, r)
    }
    else {
        nearest_fraction(r, N, r2 - Fraction::from_int(c), f2, f3)
    }
}

fn F(r: Fraction, N: i128) -> Fraction {
    if r.den <= N {
        return r
    }
    else {
        nearest_fraction(r, N, r, Fraction { num: 1, den: 0 },
                                    Fraction { num: 0, den: 1 })
    }
}

fn main() {
    let (r, N) = read_input();
    let frac = F(r, N);
    println!("{} {}", frac.num, frac.den)
}