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

number_of_solutions.rs

#![deny(overflowing_literals)]

type Number = u32;
//Верхняя граница на входные данные
const BOUND: Number = 1_000_000_000;

//Вычисляет число делителей квадрата аргумента
fn number_of_divisors_of_square(mut n: Number) -> Number {
    let mut acc = 1;
    
    //Для всех целых чисел от 2 до квадратного корня из аргумента
    for i in 2..=(Into::<f64>::into(n).sqrt().ceil() as Number) {
        let mut power = 0;
        while n % i == 0 { //считаем, в какой степени i входит в разложение n
            n /= i;
            power += 1;
        }
        acc *= 2*power + 1; //Для n = a1^q1 * a2^q2 * ... * ak^qk, где ai -- простые,
                            //число делителей равно tau(n) = (q1 + 1)*(q2 + 1)*...*(qk + 1).
                            //Для n^2 = a1^(2*q1) * a2^(2*q2) * ... * ak^(2*qk)
                            //соответственно tau(n^2) = (2*q1 + 1)*(2*q2 + 1)*...*(2*qk + 1)
    }
    
    if n > 1 {
       //Если n ещё не обратилось в единицу после переборов всех делителей, то
       //оно -- простое, и n = n^1, поэтому для получения окончательного
       //домножаем на 2*1 + 1 = 3
       acc *= 3;
    }
    
    acc
}

#[derive(Debug, PartialEq)]
enum NumSolutionsError { //Тип возможной ошибки при вычислении ответа
    OutOfBound, //Входное значение превышает BOUND
}

//Для данного n возвращает число натуральных решений уравнений 1/n = 1/x + 1/y
//или ошибку, если n слишком велико
fn number_of_solutions(n: Number) -> Result<Number, NumSolutionsError> {
    match n {
        bigger if bigger >= BOUND => Err(NumSolutionsError::OutOfBound),
        0 => Ok(0),
        1 => Ok(1),
        _ => Ok(number_of_divisors_of_square(n)),
    }
}

#[test]
//Проверим на первых числах
fn check_seq() {
    //Готовые решения (http://oeis.org/A048691)
    let answers = 
        vec![
            0, 1, 3, 3, 5, 3, 9, 3, 7, 5, 9, 3, 15, 3,
            9, 9, 9, 3, 15, 3, 15, 9, 9, 3, 21, 5, 9, 7,
            15, 3, 27, 3, 11, 9, 9, 9, 25, 3, 9, 9, 21, 3,
            27, 3, 15, 15, 9, 3, 27, 5, 15, 9, 15, 3, 21, 9,
            21, 9, 9, 3, 45, 3, 9, 15, 13, 9, 27, 3, 15, 9, 
            27, 3, 35, 3, 9, 15, 15, 9, 27, 3, 27
        ];

    //Для каждого целого n до количества готовых решений проверяем,
    //что готовое решение и решение, даваемое функцией, совпадают
    for (answer, n) in answers.into_iter().zip(0..) {
        assert_eq!(number_of_solutions(n), Ok(answer));
    }
}

#[test]
//Проверяем корректную обработку слишком больших чисел
fn check_error() {
    assert_eq!(number_of_solutions(BOUND), Err(NumSolutionsError::OutOfBound));
}

Решение rev. 1 (медленное и оверинженирнутое): https://play.rust-lang.org/?gist=e88fe63347180ef212c0da77bf7a58f4&version=stable

Решение rev. 2: https://play.rust-lang.org/?gist=2f72bf3fd02c7d4c51bfa907ea541057&version=nightly