Algorithm notes on the back of used envelopes bound in a ring binder

• Q.2 Even Fibonacci numbers
• Q.26 Reciprocal cycles
• Binary Exponentiation - CP-Algorithms

fn conservative_mod_pow(a: u64, exp: u64, m: u64) -> u64 {
    let mut result = 1;
    for _ in 0..exp {
        result *= a;
        result %= m;
    }
    result
}

fn main() {
    let m = 10_000_000_000;
    let mut sum = 0u64;
    for n in 1..=1000 {
        sum += conservative_mod_pow(n, n, m);
        sum %= m;
    }

    println!("{}", sum);
    assert_eq!(sum, 9110846700);
}

fn mod_pow(a: u64, exp: u64, m: u64) -> u64 {
    let (mut a, mut exp, m) = (a as u128, exp as u128, m as u128);
    if m == 1 {
        return 0;
    }
    if exp == 0 {
        return 1;
    }
    let mut result = 1;
    a %= m;
    loop {
        if exp % 2 == 1 {
            result *= a;
            result %= m;
        }
        exp >>= 1;
        if exp == 0 {
            break;
        }
        a *= a;
        a %= m;
    }
    result as u64
}

fn main() {
    let m = 10_000_000_000u64;
    let mut sum = 0u64;
    for n in 1..=1000 {
        sum += mod_pow(n, n, m);
        sum %= m;
    }

    println!("{}", sum);
    assert_eq!(sum, 9110846700);
}