AtCoder Beginner Contest 363 F

https://atcoder.jp/contests/abc363/tasks/abc363_f

分割を全部出してそこから題意に合うものを出力すればいいと思ったのですが、それでは間に合わず、それなりに絞って行かないといけないです。

// Palindromic Expression
#![allow(non_snake_case)]


//////////////////// 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()
}


//////////////////// Factors ////////////////////

fn div_pow(n: i64, d: i64) -> (u32, i64) {
    if n % d == 0 {
        let (e, m) = div_pow(n / d, d);
        (e + 1, m)
    }
    else {
        (0, n)
    }
}

struct Factors {
    fs: Vec<(i64, u32)>
}

impl Factors {
    fn is_one(&self) -> bool {
        self.fs.is_empty()
    }
    
    fn len(&self) -> usize {
        self.fs.len()
    }
    
    fn copy(&self) -> Factors {
        Factors { fs: self.fs.to_vec() }
    }
    
    fn value(&self) -> i64 {
        let mut n = 1;
        for &(p, e) in self.fs.iter() {
            n *= p.pow(e)
        }
        n
    }
    
    fn divisors(&self) -> Vec<(Factors, Factors)> {
        if self.is_one() {
            vec![(Factors::one(), Factors::one())]
        }
        else if self.len() == 1 {
            let (p, e) = self.fs[0];
            let mut v: Vec<(Factors, Factors)>
                            = vec![(Factors::one(), self.copy())];
            for e1 in 1..e {
                v.push((Factors { fs: vec![(p, e1)] },
                        Factors { fs: vec![(p, e-e1)] }))
            }
            v.push((self.copy(), Factors::one()));
            v
        }
        else {
            let mut v: Vec<(Factors, Factors)> = vec![];
            let mid = self.len() / 2;
            let fs1 = Factors { fs: self.fs[..mid].to_vec() };
            let fs2 = Factors { fs: self.fs[mid..].to_vec() };
            let pairs1 = fs1.divisors();
            let pairs2 = fs2.divisors();
            for (fs11, fs12) in pairs1.iter() {
                for (fs21, fs22) in pairs2.iter() {
                    v.push((fs11.copy() * fs21.copy(),
                            fs12.copy() * fs22.copy()))
                }
            }
            v
        }
    }
    
    fn one() -> Factors {
        Factors { fs: vec![] }
    }
    
    fn factorize(mut n: i64) -> Factors {
        let mut fs = vec![];
        for p in 2.. {
            if p * p > n {
                break
            }
            if n % p == 0 {
                let (e, m) = div_pow(n, p);
                fs.push((p, e));
                n = m;
            }
        }
        
        if n != 1 {
            fs.push((n, 1))
        }
        Factors { fs }
    }
}

use std::ops::Mul;

impl Mul for Factors {
    type Output = Self;
    
    fn mul(self, other: Self) -> Self {
        let mut fs = self.fs.to_vec();
        for &a in other.fs.iter() {
            fs.push(a)
        }
        Self { fs }
    }
}


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

fn includes_zero(mut n: i64) -> bool {
    while n != 0 {
        let d = n % 10;
        if d == 0 {
            return true
        }
        n /= 10
    }
    false
}

fn reverse_number(mut n: i64) -> i64 {
    let mut m: i64 = 0;
    while n != 0 {
        let d = n % 10;
        m = m * 10 + d;
        n /= 10
    }
    m
}

fn divide(fs: &Factors, mut n: i64) -> Factors {
    let mut v: Vec<(i64, u32)> = vec![];
    for &(p, e) in fs.fs.iter() {
        let (e1, n1) = div_pow(n, p);
        if e1 < e {
            v.push((p, e - e1))
        }
        n = n1
    }
    Factors { fs: v }
}

fn divisors(fs: &Factors, lower: i64) -> Vec<i64> {
    let n = fs.value();
    let r = reverse_number(n);
    if n == r && !includes_zero(n) {
        return vec![n]
    }
    
    let pairs = fs.divisors();
    for (fs1, fs2) in pairs.into_iter() {
        if fs1.is_one() || fs2.is_one() {
            continue
        }
        let n1 = fs1.value();
        if includes_zero(n1) || n1 < lower {
            continue
        }
        let r1 = reverse_number(n1);
        let n2 = fs2.value();
        if n2 % r1 != 0 {
            continue
        }
        let fs3 = divide(&fs2, r1);
        if fs3.is_one() {
            return vec![n1, r1]
        }
        
        let mut ds3 = divisors(&fs3, n1);
        if !ds3.is_empty() {
            ds3.insert(0, n1);
            ds3.push(r1);
            return ds3
        }
    }
    vec![]
}

fn F(N: i64) -> String {
    let fs = Factors::factorize(N);
    let ds = divisors(&fs, 1);
    if !ds.is_empty() {
        ds.into_iter().map(|d| d.to_string()).collect::<Vec<String>>().join("*")
    }
    else {
        String::from("-1")
    }
}

fn main() {
    let N: i64 = read();
    println!("{}", F(N))
}