アルゴリズムと数学 013

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

ナイーブに素因数分解して、あとは分割統治法的に約数を列挙します。

// Divisor Enumeration
#![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 ////////////////////

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

impl Factors {
    fn len(&self) -> usize {
        self.fs.len()
    }
    
    fn divisors(&self) -> Vec<i64> {
        if self.len() == 1 {
            let mut ds: Vec<i64> = vec![1];
            let (p, e) = self.fs[0];
            let mut d = 1;
            for _ in 0..e {
                d *= p;
                ds.push(d)
            }
            ds
        }
        else {
            let mid = self.len() / 2;
            let fs1: Vec<(i64, i32)> = (0..mid).map(|i| self.fs[i]).collect();
            let fs2: Vec<(i64, i32)> = (mid..self.len()).
                                                map(|i| self.fs[i]).collect();
            let ds1 = (Factors { fs: fs1 }).divisors();
            let ds2 = (Factors { fs: fs2 }).divisors();
            ds1.iter().map(|d1| ds2.iter().map(|d2| d1 * d2).
                        collect::<Vec<i64>>()).flatten().collect::<Vec<i64>>()
        }
    }
    
    fn create(n: i64) -> Factors {
        Factors { fs: Factors::create_core(n, 2) }
    }
    
    fn create_core(n: i64, p0: i64) -> Vec<(i64, i32)> {
        if n == 1 {
            return vec![]
        }
        
        match (p0..).take_while(|p| p * p <= n).
                                    filter(|p| n % p == 0).next() {
            Some(p) => {
                            let (e, m) = Factors::div_pow(n, p);
                            let mut fs = vec![(p, e)];
                            let fs1 = Factors::create_core(m, p + 1);
                            for f in fs1.into_iter() {
                                fs.push(f)
                            }
                            fs
                        },
            None    => vec![(n, 1)]
        }
    }
    
    fn div_pow(n: i64, p: i64) -> (i32, i64) {
        let mut m = n;
        let mut e = 0;
        while m % p == 0 {
            e += 1;
            m /= p
        }
        (e, m)
    }
}


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

fn f(N: i64) {
    let fs = Factors::create(N);
    let ds = fs.divisors();
    for d in ds.iter() {
        println!("{}", d)
    }
}

fn main() {
    let N: i64 = read();
    f(N)
}