アルゴリズムと数学 052

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

(1, 2)方向にx歩、(2, 1)方向にy歩進んで(X, Y)に到達するとすると、

となるので、xとyが0以上の整数になればよいです。しかし、一方が整数になればもう一方も整数になるので、X + Yが3の倍数かを調べればよいです。

// Knight
#![allow(non_snake_case)]


//////////////////// constants ////////////////////

const D: i64 = 1000000007;


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

// ax = by + 1 (a, b > 0)
fn linear_diophantine(a: i64, b: i64) -> Option<(i64, i64)> {
    if a == 1 {
        return Some((1, 0))
    }
    
    let q = b / a;
    let r = b % a;
    if r == 0 {
        return None
    }
    let (x1, y1) = linear_diophantine(r, a)?;
    Some((-q * x1 - y1, -x1))
}

fn inverse(a: i64, d: i64) -> i64 {
    let (x, _y) = linear_diophantine(a, d).unwrap();
    if x >= 0 {
        x % d
    }
    else {
        x % d + d
    }
}


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

fn read_input() -> (i64, i64) {
    let v = read_vec();
    (v[0], v[1])
}

fn C(n: i64, m: i64) -> i64 {
    (0..m).fold(1, |x, y| x * (n-y) % D * inverse(y+1, D) % D)
}

fn f(X: i64, Y: i64) -> i64 {
    if (X + Y) % 3 != 0 {
        0
    }
    else {
        let x = (-X + 2*Y) / 3;
        let y = (2*X - Y) / 3;
        if x >= 0 && y >= 0 {
            C(x + y, x)
        }
        else {
            0
        }
    }
}

fn main() {
    let (X, Y) = read_input();
    println!("{}", f(X, Y))
}

アルゴリズムと数学 051

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

単なる組合せですね。

// Combination Hard
#![allow(non_snake_case)]


//////////////////// constants ////////////////////

const D: i64 = 1000000007;


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

// ax = by + 1 (a, b > 0)
fn linear_diophantine(a: i64, b: i64) -> Option<(i64, i64)> {
    if a == 1 {
        return Some((1, 0))
    }
    
    let q = b / a;
    let r = b % a;
    if r == 0 {
        return None
    }
    let (x1, y1) = linear_diophantine(r, a)?;
    Some((-q * x1 - y1, -x1))
}

fn inverse(a: i64, d: i64) -> i64 {
    let (x, _y) = linear_diophantine(a, d).unwrap();
    if x >= 0 {
        x % d
    }
    else {
        x % d + d
    }
}


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

fn read_input() -> (i64, i64) {
    let v = read_vec();
    (v[0], v[1])
}

fn C(n: i64, m: i64) -> i64 {
    (0..m).fold(1, |x, y| x * (n-y) % D * inverse(y+1, D) % D)
}

fn main() {
    let (X, Y) = read_input();
    println!("{}", C(X + Y, Y))
}

アルゴリズムと数学 050

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

繰り返し2乗法というやつですね。

// Power
#![allow(non_snake_case)]


//////////////////// constants ////////////////////

const D: u64 = 1000000007;


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


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

fn read_input() -> (u64, u64) {
    let v = read_vec();
    (v[0], v[1])
}

fn f(a: u64, b: u64) -> u64 {
    if b == 1 {
        a
    }
    else if b % 2 == 0 {
        let n = f(a, b / 2);
        n * n % D
    }
    else {
        f(a, b - 1) * a % D
    }
}

fn main() {
    let (a, b) = read_input();
    println!("{}", f(a, b))
}

アルゴリズムと数学 049

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

までなので、の解法で十分ですね。
手元ではPythonのような、

(a, b) = (b, (a + b) % D)

というコードが通りましたが、AtCoderでは通りませんね。

// Fibonacci Easy (mod 1000000007)
#![allow(non_snake_case)]


//////////////////// constants ////////////////////

const D: i64 = 1000000007;


//////////////////// 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 f(N: i64) -> i64 {
    let mut a: i64 = 1;
    let mut b: i64 = 1;
    for _ in 2..N {
//      (a, b) = (b, (a + b) % D)
        let tmp = a;
        a = b;
        b = (tmp + b) % D
    }
    b
}

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

AtCoder Beginner Contest 300 E

https://atcoder.jp/contests/abc300/tasks/abc300_e

例えば6なら、確率をで表すとすると、

なので、

となります。一般には、

と書けます。

メモを関数の外に持つのはクレートを使わないと難しそう。

// Dice Product 3
#![allow(non_snake_case)]

use std::collections::HashMap;


//////////////////// constants ////////////////////

const D: u64 = 998244353;


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

// ax = by + 1 (a, b > 0)
fn linear_diophantine(a: i64, b: i64) -> Option<(i64, i64)> {
    if a == 1 {
        return Some((1, 0))
    }
    
    let q = b / a;
    let r = b % a;
    if r == 0 {
        return None
    }
    let (x1, y1) = linear_diophantine(r, a)?;
    Some((-q * x1 - y1, -x1))
}

fn inverse(a: i64, d: i64) -> i64 {
    let (x, _y) = linear_diophantine(a, d).unwrap();
    if x >= 0 {
        x % d
    }
    else {
        x % d + d
    }
}


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

fn f(N: u64, memo: &mut HashMap<u64, u64>) -> u64 {
    if N == 1 {
        1
    }
    else if memo.get(&N) != None {
        *memo.get(&N).unwrap()
    }
    else {
        let inv5 = inverse(5, D as i64) as u64;
        let x = (2..7).filter(|d| N % d == 0).
                    map(|d| f(N/d, memo)).sum::<u64>() * inv5 % D;
        memo.insert(N, x);
        x
    }
}

//////////////////// main ////////////////////

fn main() {
    let N: u64 = read();
    let mut memo = HashMap::new();
    println!("{}", f(N, &mut memo))
}

AtCoder Beginner Contest 300 D

https://atcoder.jp/contests/abc300/tasks/abc300_d

しらみつぶしで十分ですね。
エラトステネスの篩を実装してみました。

// AABCC
#![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 make_prime_table(N: usize) -> Vec<usize> {
    let mut a: Vec<bool> = (0..N+1).map(|_| true).collect();
    for p in 2usize.. {
        if p * p > N {
            break
        }
        else if !a[p] {
            continue
        }
        for m in (p*p..N+1).step_by(p) {
            a[m] = false
        }
    }
    (2..N+1).filter(|&n| a[n]).collect::<Vec<usize>>()
}


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

fn f(N: usize) -> usize {
    let ps = make_prime_table(((N/12) as f64).sqrt() as usize);
    let mut counter: usize = 0;
    for i in 0..ps.len()-2 {
        let a = ps[i];
        if a * a * ps[i+1] * ps[i+2] * ps[i+2] > N {
            break
        }
        let M = N / (a * a);
        for j in i+1..ps.len()-1 {
            let b = ps[j];
            if b * ps[j+1] * ps[j+1] > M {
                break
            }
            let L = M / b;
            for k in j+1..ps.len() {
                let c = ps[k];
                if c * c > L {
                    break
                }
                counter += 1
            }
        }
    }
    counter
}

//////////////////// main ////////////////////

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

アルゴリズムと数学 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))
}