这个题目挺有意思的,想了很久来怎么做,也查了很久。
这种形式的幂取模已经不太能用快速幂取模来求了。一来是幂运算是不支持交换律的,二来是如果算的话,数会很大。
这个题目的特别是,只求最后一位。
那么我们就能找规律。规律就是每一个数的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);
    }
}

标签: none

添加新评论