アルゴリズムと数学 048

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

最初に、2と5の素因数があれば5と2を掛ければ10のべき乗になるので排除できます。例えば、12なら25を掛けて300なので、3を考えればよいです。
29を考えてみましょう。100000000000001が29で割り切れます。要するに、です。これはどういうことかというと、10のべき乗を29で割ると余りは、

1, 10, 13, 14, 24, 8, 22, 17, 25, 18, 6, 2, 20, 26,
28, 19, 16, 15, 5, 21, 7, 12, 4, 11, 23, 27, 9, 3, 1, ...

となります。だから、周期28となることがわかります。とおくと、だから、で、実際に計算するとなりました。
10のべき乗を31で割ると余りは、

1, 10, 7, 8, 18, 25, 2, 20, 14, 16, 5, 19, 4, 9, 28, 1, ...

なので、10のべき乗で30になるものがありません。こういうときは10のべき乗を足して-1になるペアを探します。それでもなければさらに10のべき乗を足していきます。高速化のために少し工夫が要ります。

// Small Multiple
#![allow(non_snake_case)]

use std::collections::HashSet;


//////////////////// 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 remove_2_and_5(mut n: i64) -> i64 {
    while n % 2 == 0 {
        n /= 2
    }
    while n % 5 == 0 {
        n /= 5
    }
    n
}

fn calc_mod_pows(N: i64) -> Vec<i64> {
    let mut v: Vec<i64> = vec![1];
    loop {
        let n = v.last().unwrap() * 10 % N;
        if n == 1 {
            break
        }
        v.push(n)
    }
    v
}

fn proceed(total_pows: &mut HashSet<i64>, current_pows: Vec<i64>,
                                        pows: &Vec<i64>, N: i64) -> Vec<i64> {
    let mut new_pows: Vec<i64> = Vec::new();
    for &x in current_pows.iter() {
        if total_pows.contains(&(x+1)) {
            continue
        }
        for &p in pows.iter() {
            let y = (x + 1) * p % N;
            total_pows.insert(y);
            new_pows.push(y)
        }
    }
    new_pows
}

fn f(K: i64) -> i64 {
    let N = remove_2_and_5(K);
    if N == 1 {
        return N
    }
    
    let pows = calc_mod_pows(N);
    let mut total_pows: HashSet<i64> = pows.iter().map(|x| *x).collect();
    let mut current_pows = pows.clone();
    for s in 2.. {
        if current_pows.contains(&(N-1)) {
            return s
        }
        current_pows = proceed(&mut total_pows, current_pows, &pows, N)
    }
    0
}

fn main() {
    let K: i64 = read();
    println!("{}", f(K))
}