アルゴリズムと数学 085（2）

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

積のほうから求める方法もありますが、手間がかかりますね。

// Two Conditions
#![allow(non_snake_case)]

use std::collections::HashMap;


//////////////////// 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 YesNo(b: bool) -> String {
    return if b { "Yes".to_string() } else { "No".to_string() }
}


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

type Factors = Vec<(u32, u32)>;

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

fn factorize(n: u32, p0: u32) -> Factors {
    if n == 1 {
        return vec![]
    }
    
    for p in p0.. {
        if p * p > n {
            break
        }
        if n % p == 0 {
            let (e, m) = div_pow(n, p);
            let factors = factorize(m, p + 1);
            let mut new_factors = vec![(p, e)];
            new_factors.extend(&factors);
            return new_factors
        }
    }
    vec![(n, 1)]
}

fn value(fs: &Factors) -> u32 {
    fs.iter().fold(1, |x, (p, e)| x * p.pow(*e))
}

fn mul(fs1: &Factors, fs2: &Factors) -> Factors {
    let mut dic: HashMap<u32, u32> = fs1.iter().map(|&f| f).collect();
    for (p, e) in fs2.into_iter() {
        let entry = dic.entry(*p).or_insert(0);
        *entry += e
    }
    let mut fs: Factors = dic.into_iter().collect();
    fs.sort();
    fs
}

fn div(fs1: &Factors, fs2: &Factors) -> Factors {
    let mut dic: HashMap<u32, u32> = fs1.iter().map(|&f| f).collect();
    for (p, e) in fs2.into_iter() {
        let entry = dic.entry(*p).or_insert(0);
        *entry -= e;
        if *entry == 0 {
            dic.remove(&p);
        }
    }
    let mut fs: Factors = dic.into_iter().collect();
    fs.sort();
    fs
}

fn divisors(fs: &Factors) -> Vec<Factors> {
    if fs.is_empty() {
        vec![fs.to_vec()]
    }
    else if fs.len() == 1 {
        let (p, e) = fs[0];
        (0..e+1).map(|e1| if e1 == 0 { vec![] } else { vec![(p, e1)] }).
                                                collect::<Vec<Factors>>()
    }
    else {
        let mid = fs.len() / 2;
        let fs1 = (0..mid).map(|i| fs[i]).collect::<Factors>();
        let fs2 = (mid..fs.len()).map(|i| fs[i]).collect::<Factors>();
        let fss1 = divisors(&fs1);
        let fss2 = divisors(&fs2);
        let mut fss: Vec<Factors> = Vec::new();
        for fs1 in fss1.iter() {
            for fs2 in fss2.iter() {
                fss.push(mul(fs1, fs2))
            }
        }
        fss
    }
}


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

fn read_input() -> (u32, u32, u32) {
    let v = read_vec();
    let N = v[0];
    let X = v[1];
    let Y = v[2];
    (N, X, Y)
}

fn divide(fs: &Factors, num_divs: u32, lower: u32) -> Vec<Vec<Factors>> {
    if num_divs == 1 {
        let x = value(fs);
        if x < lower {
            vec![]
        }
        else {
            vec![vec![fs.to_vec()]]
        }
    }
    else {
        let mut fsss: Vec<Vec<Factors>> = vec![];
        let fss1 = divisors(fs);
        for fs1 in fss1.into_iter() {
            let fs2 = div(fs, &fs1);
            let x = value(&fs1);
            if x < lower {
                continue
            }
            let fsss2 = divide(&fs2, num_divs-1, x);
            for mut fss2 in fsss2.into_iter() {
                let mut fss = vec![fs1.to_vec()];
                fss.append(&mut fss2);
                fsss.push(fss)
            }
        }
        fsss
    }
}

fn f(N: u32, X: u32, Y: u32) -> bool {
    let fs = factorize(Y, 2);
    let fsss = divide(&fs, 4, 1);
    let xss: Vec<Vec<u32>> = fsss.into_iter().
                                    map(|fss| fss.iter().map(|fs| value(fs)).
                                                collect::<Vec<u32>>()).
                                    collect();
    xss.into_iter().
        any(|xs| xs.iter().all(|x| *x <= N) && xs.iter().sum::<u32>() == X)
}

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