Решение задачи №137 от UniLecs (Multiplication of digits)

main.rs

type Number = u64;

/// Разложение числа по базовым множителям (см. ниже в комментариях)
struct DigitalFactors {
    two:   Number,
    three: Number,
    five:  Number,
    seven: Number,
}

/// Возвращает степень, с которой factor входит в разложение n,
/// и меняет n на n / factor ^ результат.
fn factor_part(n: &mut Number, factor: Number) -> Number {
    let mut degree = 0;
    
    while *n % factor == 0 {
        *n /= factor;
        degree += 1;
    }
    
    degree
}

/// Возвращает разложение n по базовым множителям
/// или None, если такого разложения не существует.
fn digit_factor(mut n: Number) -> Option<DigitalFactors> {
    if n == 0 {
        return Some(DigitalFactors { two: 0, three: 0, five: 0, seven: 0})
    }
    
    let n = &mut n;
    let two   = factor_part(n, 2);
    let three = factor_part(n, 3);
    let five  = factor_part(n, 5);
    let seven = factor_part(n, 7);
    
    if *n != 1 {
        return None
    }
    
    Some(DigitalFactors {two, three, five, seven})
}

/// Приписывает к числу n count цифр digit
fn append_digits(n: &mut Number, digit: Number, count: Number) {
    (0..count).for_each(|_| *n = *n * 10 + digit)
}

/// Возвращает минимальное число, произведение чисел которого равно n,
/// или None, если такого не существует.
fn minimal_mult(n: Number) -> Option<Number> {
    if n == 0 { return Some(0) }
    if n == 1 { return Some(1) }
    
    let DigitalFactors { two, three, five, seven } = digit_factor(n)?;
    // Число девяток в разложение равно числу троек `2`.
    // Число восьмёрок в разложении равно числу двоек `3`.
    let eight = two / 3;
    let nine = three / 2;
    
    // Оставшиеся `2` и `3` распределяем согласно таблице
    let (two, three, four, six) = match (two % 3, three % 2 == 0) {
        (0, true)  => (0, 0, 0, 0),
        (1, true)  => (1, 0, 0, 0),
        (_, true)  => (0, 0, 1, 0),
        (0, false) => (0, 1, 0, 0),
        (1, false) => (0, 0, 0, 1),
        (_, false) => (1, 0, 0, 1),
    };
    
    // Собираем число из цифр в порядке возрастания
    let acc = &mut 0;
    append_digits(acc, 2, two);
    append_digits(acc, 3, three);
    append_digits(acc, 4, four);
    append_digits(acc, 5, five);
    append_digits(acc, 6, six);
    append_digits(acc, 7, seven);
    append_digits(acc, 8, eight);
    append_digits(acc, 9, nine);
    
    Some(*acc)
}

fn main() {
    let args = [
        1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
        34, 100, 168, 216, 324, 330, 432, 648,
        1000, 2520, 4212, 7350, 21600, 30240, 1_000_000_000,
    ];
    
    for &n in &args {
        println!("{:>10} -> {:?}", n, minimal_mult(n));
    }
}

Для того, чтобы по числу n можно было построить число m, произведение цифр которого равно n, необходимо, чтобы n раскладывалось по множителям чисел в пределах первого десятка (т. е. "цифр"). Эти множители — 2, 3, 5 и 7 (1 не рассматривается, т. к. её включение не меняет значения произведения). Назовём их базовыми множителями. Если число раскладывается по базовым множителям, будем называть его цифро-разложимым. Совокупность множителей цифро-разложимого числа назовём цифровой базой числа.

Требуемое по условию задачи число можно, вообще говоря, построить по цифровой базе не единственным способом — некоторые множители можно объединить в группы, произведение составляющих которого меньше 10. Назовём цифровым факторизатором числа разбиение его цифровой базы на непустые множества (группы множителей), в которых произведение элементов меньше 10 (т. е. возможно записать одной цифрой). Надо отметить, что некоторые группы при этом могут содержать всего один множитель. Произведение множителей группы будем называть цифрой группы. Число, получающееся из цифрового факторизатора путём выписывания в порядке возрастания цифр групп, которые его составляют, назовём значением этого факторизатора.

Т. к. значения цифровых факторизаторов — обычные числа, на множестве цифровых факторизаторов можно задать отношение порядка, порождённое отношением порядка их значений. Множество всех цифровых факторизаторов, построенных по данной цифровой базе, является, очевидно, конечным (в силу того, что данное множество является подмножеством множества всех разбиений множителей цифровой базы по множеством, а оно конечно в силу конечности цифровой базы). В силу этого у множества всех факторизаторов данного числа существует минимальный элемент. Т. о., условие задачи (опуская обозначение -1 как ответ "решение не найдено") можно записать в наших терминах в следующем виде:

Дано натуральное число n ≤ 10⁹.
Выяснить, является ли n цифро-разложимым, и если да, то найти значение его минимального цифрового факторизатора.

Пример:
n = 12
Его цифровая база — множество {2, 2, 3}.
Цифровые факторизаторы — {(2)(2)(3), (2, 2)(3), (2)(2, 3)}, их значения — 223, 34 и 26 соответственно. Минимальное число из этого списка — 26, поэтому оно и является ответом на вопрос задачи.

Будем длиной цифрового факторизатора называть количество групп в его составе. Множители в группах из одного элемента будем называть синглетными. Отметим, что "≤ 10" — довольно жёсткое ограничение, поэтому разновидностей групп в составе факторизатора не так уж и много. Именно:

(2), (3), (5), (7),
(2, 2), (2, 3), (3, 3),
(2, 2, 2)

Как видно, группы с 5 и 7 невозможно с чем-либо объединить, поэтому изменять значение факторизатора можно, лишь комбинируя по разному 2 и 3.

Если воспринимать значения факторизаторов не как числа, а как последовательности цифр, то можно вывести следующий факт: факторизаторы одной длины можно сравнивать, сравнивая количество цифр их групп. Именно, из двух факторизаторов меньше тот, среди цифр групп которого больше 2, при равенстве их количества меньше тот, среди цифр групп которого больше 3 и т. д. Отсюда следствие: если множители нескольких групп в факторизаторе перегруппировать так, чтобы минимальная цифра групп среди них стала меньше, то сам факторизатор станет меньше. Также можно сделать факторизатор меньше, перегруппировав его множители так, чтобы уменьшить число групп (т. к. факторизатор с меньшей длиной меньше факторизатора с большей длиной).

Пример:
Пусть есть цифровой факторизатор (2, 2)(3)(5). Его значение равно 345. Цифры групп его первых двух групп — одна 3 и одна 4 (минимальная цифра — 3). Перегруппировав множители этих групп, получим факторизатор (2)(2, 3)(5). Цифры групп его первых двух групп — одна 2 и одна 6 (минимальная цифра — 2). 2 < 3, поэтому по доказанному новый факторизатор должен быть меньше. И действительно, значение нового факторизатора есть 265, что меньше 345, значения исходного факторизатора.

Лемма: если факторизатор данного числа является минимальным и включает в себя больше трёх 2, то эти три из них обязательно объединены в одну группу.
Доказательство: будем доказывать методом от противного. Покажем, что если есть минимум три 2, то факторизатор можно сделать меньше, перегруппировав его множители. Будем через →← обозначать уменьшение факторизатора за счёт уменьшения его длины, а через ↓ — уменьшение за счёт увеличения количества меньших цифр групп. Будем в каждом случае показывать только интересующую нас составляющую факторизатора. При необходимости будем через (k...) обозначать, что в среди остальных групп есть синглетная цифра k, а через (×k...) будем обозначать, что среди остальных групп факторизатора нет синглетной k.
Рассмотрим каждый возможный случай распределения трёх 2 по группам:

1. (2)(2)(2) ⇒ (2, 2, 2) →←
2. (2)(2)(2, k) ⇒ (k)(2, 2, 2) →←
3. (2, 2)(2, _):
    3.1. (2, 2)(2, 2) ⇒ (2)(2, 2, 2) ↓
    3.2. (2, 2)(2, 3) ⇒ (3)(2, 2, 2) ↓
4. (2)(2, _)(2, _):
    4.1. (2)(2, 2)(2, k) ⇒ (2, 2, 2)(2, k) →←
    4.2. (2)(2, 3)(2, 3) ⇒ (2, 2, 2)(3, 3) →←
5. (2, _)(2, _)(2, _):
    5.1. (2, 2)(2, 2)(2, 2) ⇒ (2, 2, 2)(2, 2, 2) →←
    5.2. (2, 2)(2, 2)(2, 3):
        5.2.1. (2, 2)(2, 2)(2, 3)(×2...) ⇒(2)(2, 2, 2)(2, 3) ↓
        5.2.2. (2, 2)(2, 2)(2, 3)(2...) ⇒ (3)(2, 2, 2)(2, 2, 2) ↓
    5.3. (2, 2)(2, 3)(2, 3):
        5.3.1. (2, 2)(2, 3)(2, 3)(×2...) ⇒ (2)(2, 2, 2)(3, 3) ↓
        5.3.2. (2, 2)(2, 3)(2, 3)(2...) ⇒ (2, 2)(2, 2, 2)(3, 3) →←
    5.4. (2, 3)(2, 3)(2, 3):
        5.4.1. (2, 3)(2, 3)(2, 3)(×3...) ⇒ (3)(2, 2, 2)(3, 3) ↓
        5.4.2. (2, 3)(2, 3)(2, 3)(3...) ⇒ (2, 2, 2)(3, 3)(3, 3) →←

Т. о., мы получаем факторизатор меньше, чем исходный, что противоречит минимальности исходного факторизатора. Следовательно, наше предположение неверно, и в минимальных факторизаторах с числом 2 больше трёх есть группа (2, 2, 2).◼
Фактически в силу того, что наше доказательство конструктивно, мы доказали более сильное утверждение: в минимальном факторизаторе 2 объединены в столько троек, сколько возможно.

Докажем ещё одну лемму: если факторизатор данного числа является минимальным и включает в себя больше двух 3, то эти две 3 из них обязательно объединены в одну группу.
Доказательство: используем тот же метод и обозначения, что и в предыдущем доказательстве. Используем так же тот факт, что три 2 обязательно должны быть в одной группе.

1. (3)(3) ⇒ (3, 3) →←
2. (3)(2, 3):
    2.1. (3)(2, 3)(×2...) ⇒ (2)(3, 3) ↓
    2.2. (3)(2, 3)(2...) ⇒ (2, 2)(3, 3) →←
3. (2, 3)(2, 3) ⇒ (2, 2)(3, 3) ↓ (случай (2, 3)(2, 3)(2...) невозможен согласно лемме выше)

Т. о., мы получаем факторизатор меньше, чем исходный, что противоречит минимальности исходного факторизатора. Следовательно, наше предположение неверно, и в минимальных факторизаторах с числом 3 больше двух есть группа (3, 3).◼
Так же, как и в прошлом случае, есть непосредственное следствие из этой леммы: в минимальном факторизаторе 3 объединены в столько пар, сколько возможно.

Комбинируя полученные выше следствия, получаем, что в минимальном факторизаторе число 2 вне троек меньше 3 и число 3 вне пар меньше двух. Для таких количеств оставшихся множителей 2 и 3 их оптимальные объединения несложно найти перебором.

2↓\3→	0	1
0	∅	(3)
1	(2)	(2, 3)
2	(2, 2)	(2)(2, 3)

Объединяя всё вышесказанное, получаем следующий факт, на основе которого можно писать программу: для того, чтобы получить минимальный факторизатор данного цифро-разложимого числа, нужно найти его цифровую базу, объединить по максимуму 2 в тройки, а 3 в пары, а оставшиеся 2 и 3 объединить согласно таблице.