这个题目挺有意思的,想了很久来怎么做,也查了很久。
这种形式的幂取模已经不太能用快速幂取模来求了。一来是幂运算是不支持交换律的,二来是如果算的话,数会很大。
这个题目的特别是,只求最后一位。
那么我们就能找规律。规律就是每一个数的N次方的个位数都只有4个数,并且在这4个数里循环。
并且我们可以加些优化,来保证结果。这个优化就是,可以简化成底数的最后两位来进行运算。
即x%100。
那么做法就是,把指数一个个从右往左的运算,然后对4取余。注意会有0的情况。
关键还是看代码吧。
fn main() {
println!("Hello, world!");
}
fn cal_n(n: u64) -> i32 {
if n < 4 {
n as i32
} else {
(n % 4 + 4) as i32
}
}
fn last_digit(lst: &[u64]) -> u64 {
let mut n = 1u64;
for i in lst.iter().rev() {
let x = if *i >= 1000 { *i % 100 } else { *i };
n = (x as f64).powi(if n < 4 {
n as i32
} else {
(n % 4 + 4) as i32
}) as u64;
}
n % 10
}
#[test]
fn basic_tests() {
let tests = vec![
(vec![], 1),
(vec![0, 0], 1),
(vec![0, 0, 0], 0),
(vec![1, 2], 1),
(vec![3, 4, 5], 1),
(vec![4, 3, 6], 4),
(vec![7, 6, 21], 1),
(vec![12, 30, 21], 6),
(vec![2, 2, 2, 0], 4),
(vec![937640, 767456, 981242], 0),
(vec![123232, 694022, 140249], 6),
(vec![499942, 898102, 846073], 6)
];
for test in tests {
assert_eq!(last_digit(&test.0), test.1);
}
}