Решение задачи №82 от UniLecs

diophantine_equation.rs

#![feature(range_contains)]
//^Строго говоря, необязательно, но проверку на принадлежность диапозону
//удобнее всего делать с этой фичей

type Coeff = i64;

//Расширенный алгоритм Евклида (рекурсивный вариант)
fn gcd_extended_recursive(a: Coeff, b: Coeff) -> (Coeff, Coeff, Coeff) {
    if b == 0 {
        (a, 1, 0)
    } else {
        match gcd_extended(b, a % b) {
            (d, x, y) => (d, y, x - (a / b) * y),
        }
    }
}

//Расширенный алгоритм Евклида (итеративный вариант).
//Не использует стек, который имеет свойство кончаться
fn gcd_extended(first: Coeff, second: Coeff) -> (Coeff, Coeff, Coeff) {
    let mut buf = Vec::new();
    let (mut a, mut b) = (first, second);
    
    while b != 0 {
        buf.push((a, b));
        a %= b;
        std::mem::swap(&mut a, &mut b);
    }
    
    let (x, y) = buf.into_iter().rev().fold((1, 0), |(x, y), (a, b)| {
        (y, x - (a / b) * y)
    });
    
    (a, x, y)
}

#[deny(overflowing_literals)]
//Верхняя граница на коэффициенты
const BOUND: Coeff = 1_000_000_000;

#[derive(PartialEq, Debug)]
//Тип возможной ошибки при решении уравнения
enum EquationErr {
    OutOfBounds(Coeff), //Данный коэффициент вышел за рамки дозволенного
}

//Возвращает решение уравнения, если оно есть, None, если его нет,
//и ошибку, если хотя бы один из коэффициентов вышел из допустимого диапозона
fn solve_equation(a: Coeff, b: Coeff) -> Result<Option<(Coeff, Coeff)>, EquationErr> {
    if !(0..=BOUND).contains(a) {
        return Err(EquationErr::OutOfBounds(a));
    }
    if !(0..=BOUND).contains(b) {
        return Err(EquationErr::OutOfBounds(b));
    }
    
    match gcd_extended(a, b) {
        (1, x, y) => { //Если a и b взаимно просты, то наличествует частное решение,
            if x < 0 { //которое при необходимости
                Ok(Some((x + b, y - a))) //корректируется, чтобы сделать x неотрицательным,
            } else {
                Ok(Some((x, y)))
            }
        },
        _ => Ok(None), //в противном случае решения нет
    }
}

//---------------------------- Тесты ----------------------------

#[test]
//Некоторые варианты (в том числе из примеров UniLecs)
fn some_variants() {
    assert_eq!(solve_equation(7, 11).unwrap(), Some((8, -5)));
    assert_eq!(solve_equation(5,  3).unwrap(), Some((2, -3)));
    assert_eq!(solve_equation(7, 77).unwrap(), None);
    assert_eq!(solve_equation(8, 64).unwrap(), None);
}

#[test]
//Проверка корректной обработки ошибочных коэффициентов
fn bound_checks() {
    use EquationErr::*;
    assert_eq!(solve_equation(-1, 4),        Err(OutOfBounds(-1)));
    assert_eq!(solve_equation(BOUND + 1, 4), Err(OutOfBounds(BOUND + 1)));
    assert_eq!(solve_equation(4, BOUND + 3), Err(OutOfBounds(BOUND + 3)));
}

Playground: https://play.rust-lang.org/?gist=a2cf4841ab65b686d5788c7ac1eb0c24&version=nightly