通过欧拉计划学Rust编程(第500题)

由于研究Libra等数字货币编程技术的需要,学习了一段时间的Rust编程,一不小心刷题上瘾。

“欧拉计划”的网址: https://projecteuler.net

英文如果不过关,可以到中文翻译的网站: http://pe-cn.github.io/

这个网站提供了几百道由易到难的数学问题,你可以用任何办法去解决它,当然主要还得靠编程,编程语言不限,论坛里已经有Java、C#、Python、Lisp、Haskell等各种解法,当然如果你直接用google搜索答案就没任何乐趣了。

这次解答的是第500题:

https://projecteuler.net/problem=500

题目描述:

120的因子个数为16,事实上120是最小的有16个因子的数。

找出最小的有2^500500个因子的数,给出这个数除以500500507的余数。

解题过程:

直接看最终的问题,2^500500是个天文数字,肯定不能用蛮力。遇到一个复杂的问题,可以先尝试解决简单的情况,然后慢慢逼近最终的问题。

第一步: 从简单的情况入手找规律:

第650题里解决过因子个数的公式,还可以计算出所有因子之和。

fn min_number_has_factors(x: u64) -> u64 {      for n in 2.. {          let groups = factors_group(n);          let factors_num = groups.iter().map(|(_, x)| x + 1).product::<u64>();          if factors_num == x {              println!("{}, divisors num: {}", n, factors_num);              print_factors_group(groups);              return n;          }      }      0  }    // 如果一个数有这些因子:[2, 2, 3, 3, 3, 3, 5, 7]  // 则得到:[(2,2), (3,4), (5,1), (7,1)]  fn factors_group(n: u64) -> Vec<(u64, u64)> {      let factors = primes::factors(n);      let groups = factors          .iter()          .group_by(|e| **e)          .into_iter()          .map(|(k, group)| (k, group.count() as u64))          .collect::<Vec<(u64, u64)>>();      groups  }    fn print_factors_group(groups: Vec<(u64, u64)>) {      println!(          "{}",          &groups              .iter()              .map(|(k, v)| k.to_string() + &"^" + &v.to_string())              .join(" * ")      );      println!(          "divisors num:  {}",          &groups              .iter()              .map(|(_, v)| "(".to_string() + &v.to_string() + &"+1)")              .join(" * ")      );  }

现在先尝试计算几个,慢慢寻找规律。

min_number_has_factors(4); // 2^2  min_number_has_factors(8); // 2^3  min_number_has_factors(16); // 2^4  min_number_has_factors(32); // 2^5  min_number_has_factors(64); // 2^6  min_number_has_factors(128); // 2^7  min_number_has_factors(256); // 2^8

结果有:

6 = 2^1 * 3^1  因子个数 4=  (1+1) * (1+1)    24 = 2^3 * 3^1  因子个数 8 = (3+1) * (1+1)    120 = 2^3 * 3^1 * 5^1  因子个数 16 =  (3+1) * (1+1) * (1+1)    840 = 2^3 * 3^1 * 5^1 * 7^1  因子个数 32 = (3+1) * (1+1) * (1+1) * (1+1)    7560 = 2^3 * 3^3 * 5^1 * 7^1  因子个数 64 = (3+1) * (3+1) * (1+1) * (1+1)    83160 = 2^3 * 3^3 * 5^1 * 7^1 * 11^1  因子个数 128 = (3+1) * (3+1) * (1+1) * (1+1) * (1+1)    1081080 = 2^3 * 3^3 * 5^1 * 7^1 * 11^1 * 13^1  因子个数 256 = (3+1) * (3+1) * (1+1) * (1+1) * (1+1) * (1+1)

第二步: 努力寻找规律

通过分析几个简单的特例,将一般性的公式推导出来,需要运用基础的数学知识。

一个数n可以分解成如下形式,其中pi为素数因子。

image

那么,它的因子个数为:

image

最终的因子个数可以表示为2 ^ 500500形式,令:

image

则有:

image

最终的结果要让[b0, b1, b2…bi]的和为500500。现在来看一下这个数组是如何变化的,找出递推的规律。

image

因子个数 2 =  (2^1)  [b0] = [1]    因子个数 4 =  (2^1) * (2^1)  [b0,b1] = [1,1]    因子个数 8 = (2^2) * (2^1)  [b0,b1] = [2,1]    因子个数 16 =  (2^2) * (2^1) * (2^1)  [b0,b1,b2] = [2,1,1]    因子个数 32 = (2^2) * (2^1) * (2^1) * (2^1)  [b0,b1,b2] = [2,2,1]    因子个数 64 = (2^2) * (2^2) * (2^1) * (2^1)  [b0,b1,b2,b3] = [2,2,1,1]    因子个数 128 = (2^2) * (2^2) * (2^1) * (2^1) * (2^1)  [b0,b1,b2,b3,b4] = [2,2,1,1,1]    因子个数 256 =  (2^2) * (2^2) * (2^1) * (2^1) * (2^1) * (2^1)  [b0,b1,b2,b3,b4,b5] = [2,2,1,1,1,1]

这里需要足够的耐心,这个bi数组或者在末尾增加一个元素1,或者在前面的某个位置上数值增1。

image

如果其中的某一项增1,则数值增加:

image

如果尾部增加一项,数值增加:

image

上面的数值中,哪一项更小,则表示或者在尾部增加一个,或者原数组中的数值增1。

最后的代码:

fn p500(n: usize) -> u64 {      let mut pset = PrimeSet::new();      let primes: Vec<_> = pset.iter().take(n).collect();      let primes_log: Vec<_> = primes.iter().map(|x| (*x as f64).log10()).collect();        let mut b = vec![1];      for _i in 2..=n {          let mut min = primes_log[b.len()];          let mut pos = b.len(); // 默认尾部增加一个          for j in 0..b.len() {              let temp = 2_f64.powf(b[j] as f64) * primes_log[j];              if temp < min {                  pos = j;                  min = temp;              }              if b[j] == 1 {                  break; // 后面的都不用判断了              }          }          if pos == b.len() {              b.push(1);          } else {              b[pos] += 1;          }      }        let mut result = 1_u64;      for i in 0..b.len() {          let exp = 2_u32.pow(b[i]) - 1;          for _j in 0..exp {              result = result * primes[i] % 500500507;          }      }      result  }

— END —

我把解决这些问题的过程记录了下来,写成了一本《用欧拉计划学 Rust 编程》PDF电子书,请随意下载。

链接:https://pan.baidu.com/s/1NRfTwAcUFH-QS8jMwo6pqw

提取码:qfha

由于欧拉计划不让发布100题之外的解题步骤,否则封号,所以最新PDF不再公开,请加我微信(SLOFSLB)索要最新的PDF电子书。