由於研究Libra等數字貨幣編程技術的需要，學習了一段時間的Rust編程，一不小心刷題上癮。 “歐拉計劃”的網址： "https://projecteuler.net" 英文如果不過關，可以到中文翻譯的網站： http://pe cn.github.io/ 這個網站提供了幾百道由易到難的數學問題，你 ...
由於研究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為素數因數。
那麼，它的因數個數為：
最終的因數個數可以表示為2 ^ 500500形式，令：
則有：
最終的結果要讓[b0, b1, b2...bi]的和為500500。現在來看一下這個數組是如何變化的，找出遞推的規律。
因數個數 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。
如果其中的某一項增1，則數值增加：
如果尾部增加一項，數值增加：
上面的數值中，哪一項更小，則表示或者在尾部增加一個，或者原數組中的數值增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電子書。
