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)) }