Submission #1166135

---

Source Code Expand

use std::io;
use std::collections::HashMap;

static MODULO : u64 = 1000000007;
fn main (){
    let n : u64 = get_line().trim().parse().unwrap();
    //  後から気付いたけどここまでするならもっとシンプルに出来た
    let ps = Primes::new(100);
    let fss = (2..n+1).map(|n| ps.factorize(n)).collect();
    let Factors{fs:factors} = concat_factors(&fss);
    let ans = factors.values().fold(1, |acc, x| (acc*((x+1)as u64)) % MODULO);
    println!("{}",ans);
}

fn get_line() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).ok();
    buf
}

#[derive(Debug)]
struct Primes {ps : Vec<u64>}
#[derive(Debug)]
struct Factors {fs : HashMap<u64, u32>}

// TODO make this generic............
// (Monoid v) => Monoid HashMap k v
// Monoid Factors

fn concat_factors(facts : &Vec<Factors>) -> Factors {
    // want something like foldM
    let mut cat = HashMap::new();
    // FIXME : don't know what I'm doing
    for &Factors{ref fs} in facts {
        for(&p, &t) in fs.iter() {
            // https://doc.rust-lang.org/std/collections/hash_map/enum.Entry.html
            * cat.entry(p).or_insert(0) += t;
        }
    }
    Factors{fs:cat}
}

impl Primes {
    fn new(n:usize) -> Primes {
        let mut ps : Vec<bool> = vec![true;n+1];
        ps[0] = false;
        ps[1] = false;
        let upper_limit = (n as f64).sqrt().ceil() as usize;
        for i in 2..upper_limit {
            if ps[i] {
                for j in 2..(n/i)+1 {
                    ps[i*j] = false;
                }
            }
        }
        let mut primes : Vec<u64> = vec![];
        for (i, &is_prime) in ps.iter().enumerate() {
            if is_prime { primes.push(i as u64);}
        }
        Primes{ps:primes}
    }
}

impl Primes {
    fn factorize(&self, n:u64) -> Factors {
        let mut num = n;
        let mut factors = HashMap::new();
        
        for &p in &self.ps {
            if p*p > num {
                break;
            }
            
            let mut times = 0; // how many times can this prime divide it
            while num % p == 0 {
                num = num / p;
                times = times+1;
            }
            if times != 0 { factors.insert(p,times); };
        }
        if num != 1{
            factors.insert(num,1); // the last prime
        }
        Factors{fs:factors}
    }
}

Submission Info

Judge Result