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

tumblers.rs

#[derive(Debug, PartialEq)]
enum TumblerError { //Тип ошибки.
    StepIsTooLarge, //Номер шага больше MAX_BOUND
    ZeroStep, //Номер шага равен нулю (нулевого тумблера нет)
}

type Step = u32;
type FloatBase = f64;

#[deny(overflowing_literals)]
const MAX_BOUND: Step = 100_000; //Ограничение на входные данные.

//Проверяет, является ли аргумент квадратом.
fn is_square(x: Step) -> bool {
    match x & 0xF { //Извлекаем последную цифру в шестнадцатиричной системе.
        2 | 3 | 5 ... 8 | 10 ... 15 => false, //На эти цифры полный квадрат оканчиваться не может.
        0 | 1 | 4 | 9 => { //Считаем целую часть от корня
            let sqrt = FloatBase::from(x).sqrt().floor() as Step;
            sqrt * sqrt == x }, //и проверяем, совпадает ли оно при возведении в квадрат с аргументом.
        _ => unreachable!(), //Остальные варианты невозможны, но компилятор недостаточно умён, чтобы это определить
    }
}

//Возвращает состояние тумблера после n-го шага или ошибку.
//true -- тумблер включён, false -- тумблер выключен.
fn tumbler_state(n: Step) -> Result<bool, TumblerError> {
    if n == 0 {
        Err(TumblerError::ZeroStep)
    } else if n > MAX_BOUND {
        Err(TumblerError::StepIsTooLarge)
    } else {
        Ok(is_square(n))
    }
}

//Проверяем, что для всех квадратов до MAX_BOUND включительно
//метод проверки через вычисление квадратного корня не страдает
//от погрешностей, присущих вычислениям с плавающей точкой.
#[test]
fn check_sqrt_correctness() {
    let mut squares = (1..).map(|i| i * i);
    let mut square = squares.next().unwrap();
    for i in 1..MAX_BOUND+1 { //Для всех чисел от 1 до MAX_BOUND включительно
        let sqrt = FloatBase::from(i).sqrt().floor() as Step; //считаем целую часть корня.
        if i == square { //Если i является квадратом,
            assert_eq!(sqrt * sqrt, i); //то убеждаемся, что корень в квадрате равен i
            square = squares.next().unwrap(); //и считаем следующий квадрат,
        } else { 
            assert_ne!(sqrt * sqrt, i); //иначе убеждаемся, что корень не даст ложноположительную оценку
        }
    }
}

//Тесты
#[test]
fn check_squares() {
    assert_eq!(tumbler_state(6*6), Ok(true));
    assert_eq!(tumbler_state(6*6+1), Ok(false));
    
    assert_eq!(tumbler_state(55*55), Ok(true));
    assert_eq!(tumbler_state(55*55+17), Ok(false));
}

//Тест граничного случая -- n = 0
#[test]
fn check_zero() {
    assert_eq!(tumbler_state(0), Err(TumblerError::ZeroStep));
}

//Тест граничного случая -- n > MAX_BOUND
#[test]
fn check_bound() {
    assert_eq!(tumbler_state(MAX_BOUND + 1), Err(TumblerError::StepIsTooLarge))
}

Т. к. два последовательных переключения тумблера переводят тумблер в исходное состояние, для ответа на вопрос задачи достаточно определить, является ли число переключения чётным или нечётным.
Для каждого i ∈ [1, n] такого, что n mod i = 0, есть j = n div i такое, что n mod j = 0. Т. о., делители числа n можно объединить по парам, поэтому число переключений тумблера — чётное число. Единственный случай, когда это не так — когда существует i ∈ [1, n] такое, что i = j = n div i. Но это равносильно тому, что n является ненулевым полным квадратом, поэтому для ответа на вопрос задачи нужно лишь выяснить, является ли n полным квадратом.