p002#
题目#
Problem 2: Even Fibonacci numbers
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with $1$ and $2$, the first $10$ terms will be: $$1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \dots$$
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
这道题目的要求是算出Fibonacci数列的前4000000个数字中的偶数之和。
解答#
这题如果直接做，可以直接根据Fibonacci数列的规律，直接while循环判断。
$$ F(n) = F(n-1)+F(n-2) $$代码如下
1fn solve2() -> u64 {
2 let mut a = 1;
3 let mut b = 2;
4 let mut sum = 0;
5 while a <= 4_000_000 {
6 if a % 2 == 0 {
7 sum += a;
8 }
9 let next = a + b;
10 a = b;
11 b = next;
12 }
13 sum
14}很明显，这样是能算到最终结果的，最终的结果就是4613732，但这个太暴力很明显不值得我特地写一篇博客。
此时，我们好好回顾一下这个问题，要求一个fibonacci数列的所有偶数，我们在写这个数列的时候会发现数列中的偶数是隔着两个奇数就有一个偶数，如果把所有偶数剔出来，会发现满足一下的规律。
$$ F(n) = 4*F(n-1) + F(n-2) $$自此可以看出来时间复杂度从O(n)->O(n/3)。 rust代码如下
1fn solve1() -> u64 {
2 let mut a = 2;
3 let mut b = 8;
4 let mut sum = 0;
5
6 while a <= 4_000_000 {
7 sum += a;
8 let next = 4 * b + a;
9 a = b;
10 b = next;
11 }
12 sum
13}计算时间上面呢也就减少了20ns，但是这样的降低时间复杂度的操作还是很有意义的。从中我们也可以得到启发，当程序无法进行优化时，可以从数学的角度入手。下面是运行时间对比图片(我把测试增加了)。
p004#
题目#
Problem 4: Largest Palindrome Product
题目链接 题目描述:
A palindromic number reads the same both ways. The largest palindrome made from the product of two $2$-digit numbers is $9009 = 91 \times 99$.
问题:Find the largest palindrome made from the product of two $3$-digit numbers.
解答a#
同样，这题可以直接设定i和j代表两个数。直接开始循环，然后通过一个函数判断乘积是否是回文数。代码如下：
1fn is_palindrome(n: u64) -> bool {
2 let s = n.to_string();
3 s.chars().eq(s.chars().rev())
4}
5fn baolisolve() -> u64 {
6 let mut max_palindrome = 0;
7 for i in 100..999 {
8 for j in 100..999 {
9 let x = i * j;
10 if is_palindrome(x) && x >= max_palindrome {
11 max_palindrome = x;
12 }
13 }
14 }
15 max_palindrome
16}最后得到的计算时间也是相当可观了（计算时间很长）
解答b#
此时可以观察到，要求出最大的回文数，往往两个数字都需要大概900多的样子，我们可以直接从后向前循环，这样的话时间就能减少很多。
解答c#
首先引入一个结论，任何一个偶数位数的回文数都可以被11整除。在本题目中，要求最大的六位回文数，则该回文数必然有一个因数也可以被11整除。于是便可以减少部分循环次数，进一步降低时间消耗。 代码如下
1fn mathsolve() -> u64 {
2 let mut max_palindrome = 0;
3 for i in (100..999).rev() {
4 let start = if i % 11 == 0 { 999 } else { 990 };
5 let step = if i % 11 == 0 { 1 } else { 11 };
6 let mut j = start;
7 while j >= 100 {
8 let n = i * j;
9 if n <= max_palindrome {
10 break;
11 }
12 if is_palindrome(n) {
13 max_palindrome = n;
14 }
15 j -= step;
16 }
17 }
18 max_palindrome
19}最后可以看到消耗时间被降低到了微秒级别
其中 \(a,b,c\) 都是数字，且 \(a \neq 0\)。
把它按十进制展开：
\[ N = 100000a + 10000b + 1000c + 100c + 10b + a \]整理同类项可得：
\[ N = 100001a + 10010b + 1100c \]接下来把每一项提取出 11：
\[ 100001 = 11 \times 9091 \]\[ 10010 = 11 \times 910 \]\[ 1100 = 11 \times 100 \]所以：
\[ N = 11(9091a + 910b + 100c) \]因此，\(N\) 一定能被 11 整除。
任意 6 位回文数都可以写成 11 的倍数，因此：
\[ \boxed{\text{任意 6 位回文数一定能被 11 整除}} \]数学博大精深～～！
p005#
题目#
Problem 5: Smallest Multiple
题目描述:
$2520$ is the smallest number that can be divided by each of the numbers from $1$ to $10$ without any remainder.
问题:What is the smallest positive number that is evenly divisibledivisible with no remainder by all of the numbers from $1$ to $20$?
解答#
这题需要求出1-20所有数字的lcm(最小公倍数)。
$$ lcm(a,b) = \frac{a * b}{gcd(a , b)} $$代码如下
1fn gcd(mut a: u64, mut b: u64) -> u64 {
2 while b != 0 {
3 let temp = b;
4 b = a % b;
5 a = temp;
6 }
7 a
8}
9
10fn lcm(a: u64, b: u64) -> u64 {
11 a / gcd(a, b) * b
12}
13
14fn solve() -> u64 {
15 (1..20).reduce(|acc, c| lcm(acc, c)).unwrap()
16}