AtCoder Beginner Contest 448 E

https://atcoder.jp/contests/abc448/tasks/abc448_e

MDの剰余で計算すればよいです。cがl個続く10進整数は繰り返し二乗法と同様に計算できます。

// Simple Division
#![allow(non_snake_case)]


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

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

fn pow(b: i64, e: u32, D: i64) -> i64 {
    if e == 0 {
        1
    }
    else if e == 1 {
        b
    }
    else if e % 2 == 1 {
        b * pow(b, e-1, D) % D
    }
    else {
        let n = pow(b, e/2, D);
        n * n % D
    }
}


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

type RunLength = (i64, u32);

fn read_run_length() -> RunLength {
    let v: Vec<i64> = read_vec();
    let (c, l) = (v[0], v[1] as u32);
    (c, l)
}

fn read_input() -> (i64, Vec<RunLength>) {
    let v: Vec<i64> = read_vec();
    let (K, M) = (v[0], v[1]);
    let RLs: Vec<RunLength> = (0..K).map(|_| read_run_length()).collect();
    (M, RLs)
}

// dがn個続く整数
fn rep_number(d: i64, n: u32, D: i64) -> i64 {
    if n == 1 {
        d
    }
    else if n % 2 == 1 {
        (rep_number(d, n-1, D) * 10 + d) % D
    }
    else {
        let rep = rep_number(d, n/2, D);
        rep * (pow(10, n/2, D) + 1) % D
    }
}

fn F(M: i64, RLs: Vec<RunLength>) -> i64 {
    let D: i64 = 10007;
    let MD = M * D;
    let mut res: i64 = 0;
    for (c, l) in RLs {
        res = (res * pow(10, l, MD) + rep_number(c, l, MD)) % MD
    }
    res / M % D
}

fn main() {
    let (M, RLs) = read_input();
    println!("{}", F(M, RLs))
}