Submission #19217158

---

Source Code Expand

// use rand::distributions::Uniform;
// use rand::{thread_rng, Rng};
use std::cmp::max;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    // for n in 1..=100 {
    //     for m in 1..=n {
    //         let sum = n * (n + 1) / 2;
    //         let x = sum - m;
    //         let y = n;
    //         let g = gcd(x, y);
    //         let (x, y) = (x / g, y / g);
    //         let ans = solve(x, y);
    //         assert!(ans.is_some(), "x/y = {}/{} n={} m={}", x, y, n, m);
    //         let (an, am) = solve(x, y).unwrap();
    //         if an != n || am != m {
    //             println!("x/y = {}/{} n={} m={} ans={:?}", x, y, n, m, (an, am));
    //         }
    //         // println!("{}/{}", x, y);
    //     }
    // }

    // let mut rng = thread_rng();
    // loop {
    //     let n = rng.sample(Uniform::from(1..=(1e9 as i128)));
    //     let m = rng.sample(Uniform::from(1..=n));
    //     let sum = n * (n + 1) / 2;
    //     let x = sum - m;
    //     let y = n;
    //     let g = gcd(x, y);
    //     let (x, y) = (x / g, y / g);
    //     let ans = solve(x, y);
    //     assert!(ans.is_some(), "x/y = {}/{} n={} m={}", x, y, n, m);
    //     let (an, am) = solve(x, y).unwrap();
    //     assert!(an == n && am == m, "{}/{}", x, y);
    //     println!("{}/{}", x, y);
    // }

    let s: String = sc.read();
    let mut iter = s.split('/');
    let x = iter.next().unwrap().parse::<i128>().unwrap();
    let y = iter.next().unwrap().parse::<i128>().unwrap();
    let g = gcd(x, y);
    let x = x / g;
    let y = y / g;

    let n = (2 * x) / y;

    let mut ans = vec![];
    for n in max(1, n - 100)..=max(2, n + 100) {
        if let Some(m) = solve_m(n, x, y) {
            ans.push((n, m));
        }
    }

    if ans.is_empty() {
        println!("Impossible");
    } else {
        for (n, m) in ans {
            println!("{} {}", n, m)
        }
    }
}

fn solve(x: i128, y: i128) -> Option<(i128, i128)> {
    let g = gcd(x, y);
    let x = x / g;
    let y = y / g;

    let n = (2 * x) / y;

    for n in max(1, n - 3)..=max(2, n + 4) {
        if let Some(m) = solve_m(n, x, y) {
            return Some((n, m));
        }
    }
    None
}

fn solve_m(n: i128, x: i128, y: i128) -> Option<i128> {
    if (x * n) % y != 0 {
        return None;
    }

    let sum = n * (n + 1) / 2;
    let m = sum - (x * n) / y;
    if m <= 0 || n < m {
        return None;
    }

    let cxn = (sum - m) * y;
    if cxn % n != 0 {
        return None;
    }
    let cx = cxn / n;
    if cx != x {
        return None;
    }

    return Some(m);
}

fn gcd(x: i128, y: i128) -> i128 {
    if y == 0 {
        x
    } else {
        gcd(y, x % y)
    }
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> Self {
        Self(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

Submission Info

Compile Error

warning: function is never used: `solve`
  --> src/main.rs:68:4
   |
68 | fn solve(x: i128, y: i128) -> Option<(i128, i128)> {
   |    ^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

Judge Result