アルゴリズムと数学 090

https://atcoder.jp/contests/math-and-algorithm/tasks/typical90_y

10¹¹まであるので、しらみつぶしできないと思えるかもしれませんが、そうでもありません。数字を入れ替えただけなら同じ積になるからです。例えば、113、131、311は同じです。重複組み合わせを発生させて、その積+Bを計算して十進にして、元の組合せと一致すればOKです。

// Digit Product Equation
#![allow(non_snake_case)]

use itertools::Itertools;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

fn digits(mut n: u64) -> Vec<u64> {
    let mut ds: Vec<u64> = vec![];
    while n != 0 {
        let d = n % 10;
        n /= 10;
        ds.push(d)
    }
    ds
}


//////////////////// process ////////////////////

fn read_input() -> (u64, u64) {
    let v = read_vec();
    let N = v[0];
    let B = v[1];
    (N, B)
}

fn exists_valid_number(ds: Vec<u64>, B: u64, N: u64) -> bool {
    if *ds.last().unwrap() == 0 {
        return false
    }
    
    let p = ds.iter().fold(1, |x, d| x * d);
    let n = p + B;
    if n > N {
        return false
    }
    let mut ds1 = digits(n);
    if ds1.len() != ds.len() {
        return false
    }
    ds1.sort();
    ds1.into_iter().zip(ds.into_iter()).all(|(d1, d)| d1 == d)
}

fn f_for_fixed_length(L: usize, N: u64, B: u64) -> u32 {
    let mut counter: u32 = 0;
    for ds in (0..10).combinations_with_replacement(L) {
        if exists_valid_number(ds, B, N) {
            counter += 1
        }
    }
    counter
}

fn f(N: u64, B: u64) -> u32 {
    let nd = digits(N).len();
    (1..nd+1).map(|L| f_for_fixed_length(L, N, B)).sum::<u32>()
}

fn main() {
    let (N, B) = read_input();
    println!("{}", f(N, B))
}