通过欧拉计划学Rust编程（第650题）

正文

请到「今天看啥」查看全文

, n, b);

let f_all = primes::factors(b);
let f_uniq = primes::factors_uniq(b);
//println!("{:?}", f_all);
//println!("{:?}", f_uniq);

let mut d = 1 ;
for f in f_uniq {
let c = f_all.iter().filter(|&n| *n == f).count();
d *= (f.pow(c as u32 + 1 ) - 1 ) / (f- 1 );
}
//println!("D({}) = {}", n, d);

s += d;
println! ( "S({}) = {}" , n, s);
}
}

可以正确地计算出S(10)，但在计算S(11)时就会出现溢出错误。

第二步：

溢出发生在pow()函数的计算上，求排列组合数和求阶乘的运算量太大，没必要把乘积计算出来，可以将因子保存在一个向量中，不断添加和删除相应的元素即可。

extern crate num_bigint;
use num_bigint::BigUint;

fn main() {
    let mut s = 0;
    for n in 1..=100 {
        let mut factors = vec![];
        for i in 1..=n {
            let mut f = comb_factors(n, i);
            factors.append(&mut f);
        }
        factors.sort();

        let d = factors_sum(&factors);
        println!("D({}) = {:?}", n, d);

        s = (s + d) % 1_000_000_007_u64;
        println!("S({}) = {}", n, s);
    }
}

fn factors_sum(v: &Vec<u64>) -> u64 {
    let mut uniq = v.clone();
    uniq.dedup();

    let mut prod = BigUint::from(1_u64);
    for p in uniq {
        let c = v.iter().filter(|&x| *x == p).count() as u64;
        let t = (big_pow(p, c + 1) - BigUint::from(1_u64)) / (BigUint::from(p - 1));
        //println!("{} {} {}", p, c, t);
        prod = prod * t % 1_000_000_007_u64;
    }
    let prod = prod % 1_000_000_007_u64;
    prod.to_string().parse::<u64>().unwrap()
}

fn big_pow(a: u64, b: u64) -> BigUint {
    let mut prod = BigUint::from(1 as u64);
    for _i in 0..b {
        prod *= BigUint::from(a as u64);
    }
    prod
}

// va中元素已经排好序
fn vec_remove(va: &mut Vec<u64>, vb: &Vec<u64>) {
    for item in vb {
        let index = va.binary_search(&item).unwrap();
        //println!("{:?} {:?} {}", va, vb, index);
        va.remove(index);
    }
}

fn comb_factors(m: u64, n: u64) -> Vec<u64> {
    let mut factors = vec![];
    let mut x = m;
    for i in 0..n {
        let mut f = primes::factors(x);
        factors.append(&mut f);
        x -= 1;
    }
    factors.sort();
    //println!("{:?}", factors);
    for i in 2..=n {
        let f = primes::factors(i);
        //println!("{} {:?}", n, f);
        vec_remove(&mut factors, &f);
    }
    factors.to_vec()
}

这次可以很容易地计算出S(100)，但要计算S(1000)则要花相当长的时间，主要是因为数组越来越大，数组排序太花时间。

还得优化。

第三步 用HashMap

数组中元素的排序太慢，尝试换成字典来存储因子，在Rust中用HashMap来实现。比如，B(10)中含有12个2，10个3，8个5，3个7。

而B(100)中含有如下因子，字典中key是质因子，value是个数。

{97: 93, 19: 65, 83: 65, 41: 44, 59: 17, 79: 57, 61: 21, 67: 33, 2: 335, 3: 192, 37: 20, 23: 56, 31: 69, 47: 80, 13: 21, 71: 41, 7: 148, 73: 45, 11: 81,
43: 56, 17: 5, 53: 5, 5: 176, 89: 77, 29: 45}

修改后的代码：

extern crate num_bigint;
use num_bigint::BigUint;

use std::collections::HashMap;
fn main

请到「今天看啥」查看全文