アルゴリズムと数学 059

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ay

べき乗の計算をするだけですが、それでは芸がないので、周期を求めます。こうすると計算量が減る可能性があります。2のべきで10の剰余を取りますが、2と10が互いに素でないので、べき乗していっても純粋なループにはなりません。互いに素なら純粋なループになります。例えば、2と5なら、

1 -> 2 -> 4 -> 3 -> 1

とループになります。しかし、互いに素でないと後ろには一意にたどれないので、純粋なループになりません。例えば、2と10なら、

1 -> 2 <- 6

となります。ただ、進む方向には一意に決まるので、いつか一度来た値に戻ります。そのため、ρの字になります。

1 -> 2 -> 4
     ↑   ↓
     6 <- 8

このとき、周期を求めるメモリを使わない方法があります。1歩ずつ進むのと2歩ずつ進むのを比較して同じになったら、1歩ずつ進んだ方が周期分進んでいます。ただ、周期しかわからず、どこからループになるかはわかりません。

// Power of Two
#![allow(non_snake_case)]

use std::cmp::min;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}


//////////////////// process ////////////////////

fn find_period(a: u64, d: u64) -> u64 {
    let mut b = 1;
    let mut c = 1;
    for i in 1..  {
        b = b * a % d;
        c = c * a * a % d;
        if b == c {
            return i
        }
    }
    0
}

fn pow_mod(a: u64, e: u64, d: u64) -> u64 {
    if e == 0 {
        1
    }
    else if e == 1 {
        a
    }
    else if e % 2 == 0 {
        let b = pow_mod(a, e/2, d);
        b * b % d
    }
    else {
        pow_mod(a, e-1, d) * a % d
    }
}

fn f(N: u64) -> u64 {
    let period = find_period(2, 10);
    let length = min(N, N % period + period);
    pow_mod(2, length, 10)
}

fn main() {
    let N = read();
    println!("{}", f(N))
}