第92题 平方数字链
题目描述:
将一个数的所有数字的平方相加得到一个新的数,不断重复直到新的数已经出现过为止,这构成了一条数字链。
例如,
44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89
可见,任何一个到达1或89的数字链都会陷入无尽的循环。更令人惊奇的是,从任意数开始,最终都会到达1或89。
有多少个小于一千万的数最终会到达89?
解题思路:
1)各位数字的平方和
fn square_sum(n: u64) -> u64 {
n.to_string()
.chars()
.map(|x| x.to_digit(10).unwrap().pow(2) as u64)
.sum::<u64>()
}
可以用整数运算提高效率。
fn square_sum(n: u64) -> u64 {
let mut m = n;
let mut s = 0;
while m != 0 {
s += (m % 10) * (m % 10);
m /= 10;
}
s
}
2)循环求解
fn main() {
let mut count = 0;
for i in 1..10_000_000 {
if square_chain_arrive(i) == 89 {
count += 1;
}
}
println!("{}", count);
}
fn square_chain_arrive(n: u64) -> u64 {
let mut x = n;
while x != 1 && x != 89 {
x = square_sum(x);
}
x
}