アルゴリズムと数学 013

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

ナイーブに素因数分解して、あとは分割統治法的に約数を列挙します。

// Divisor Enumeration
#![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()
}


//////////////////// Factors ////////////////////

struct Factors {
    fs: Vec<(i64, i32)>
}

impl Factors {
    fn len(&self) -> usize {
        self.fs.len()
    }
    
    fn divisors(&self) -> Vec<i64> {
        if self.len() == 1 {
            let mut ds: Vec<i64> = vec![1];
            let (p, e) = self.fs[0];
            let mut d = 1;
            for _ in 0..e {
                d *= p;
                ds.push(d)
            }
            ds
        }
        else {
            let mid = self.len() / 2;
            let fs1: Vec<(i64, i32)> = (0..mid).map(|i| self.fs[i]).collect();
            let fs2: Vec<(i64, i32)> = (mid..self.len()).
                                                map(|i| self.fs[i]).collect();
            let ds1 = (Factors { fs: fs1 }).divisors();
            let ds2 = (Factors { fs: fs2 }).divisors();
            ds1.iter().map(|d1| ds2.iter().map(|d2| d1 * d2).
                        collect::<Vec<i64>>()).flatten().collect::<Vec<i64>>()
        }
    }
    
    fn create(n: i64) -> Factors {
        Factors { fs: Factors::create_core(n, 2) }
    }
    
    fn create_core(n: i64, p0: i64) -> Vec<(i64, i32)> {
        if n == 1 {
            return vec![]
        }
        
        match (p0..).take_while(|p| p * p <= n).
                                    filter(|p| n % p == 0).next() {
            Some(p) => {
                            let (e, m) = Factors::div_pow(n, p);
                            let mut fs = vec![(p, e)];
                            let fs1 = Factors::create_core(m, p + 1);
                            for f in fs1.into_iter() {
                                fs.push(f)
                            }
                            fs
                        },
            None    => vec![(n, 1)]
        }
    }
    
    fn div_pow(n: i64, p: i64) -> (i32, i64) {
        let mut m = n;
        let mut e = 0;
        while m % p == 0 {
            e += 1;
            m /= p
        }
        (e, m)
    }
}


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

fn f(N: i64) {
    let fs = Factors::create(N);
    let ds = fs.divisors();
    for d in ds.iter() {
        println!("{}", d)
    }
}

fn main() {
    let N: i64 = read();
    f(N)
}

アルゴリズムと数学 012

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

ミラー・ラビンを実装する余裕がないので、2から割っておきます。

// Primality Test
#![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 YesNo(b: bool) -> String {
    return if b { "Yes".to_string() } else { "No".to_string() }
}


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

fn f(N: i64) -> bool {
    (2..).take_while(|p| p * p <= N).all(|p| N % p != 0)
}

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

アルゴリズムと数学 007

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

包除原理ですね。これを使うために最小公倍数が要ります。

// Number of Multiples 1
#![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 gcd(n: i32, m: i32) -> i32 {
    if m == 0 {
        n
    }
    else {
        gcd(m, n % m)
    }
}

fn lcm(n: i32, m: i32) -> i32 {
    n / gcd(n, m) * m
}


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

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

fn f(N: i32, X: i32, Y: i32) -> i32 {
    let D = lcm(X, Y);
    N / X + N / Y - N / D
}

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

AtCoder Beginner Contest 286 D

https://atcoder.jp/contests/abc286/tasks/abc286_d

和を状態としたDPですね。

// Money in Hand
#![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 YesNo(b: bool) -> String {
    return if b { "Yes".to_string() } else { "No".to_string() }
}


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

fn read_input() -> (usize, Vec<(usize, usize)>) {
    let v = read_vec();
    let N: usize = v[0];
    let X: usize = v[1];
    let AB: Vec<(usize, usize)> = (0..N).map(|_| read_vec()).
                                            map(|w| (w[0], w[1])).collect();
    (X, AB)
}

fn update(v: Vec<bool>, a: usize, b: usize) -> Vec<bool> {
    let mut w = (0..(v.len()+a*b)).map(|_| false).collect::<Vec<bool>>();
    for (i, c) in v.into_iter().enumerate() {
        if c {
            for d in (0..a*b+1).step_by(a) {
                w[i+d] = true
            }
        }
    }
    w
}

fn f(X: usize, AB: Vec<(usize, usize)>) -> bool {
    let M = AB.iter().map(|(a, b)| a * b).sum::<usize>();
    if X > M {
        return false
    }
    let mut v = (0..(M+1)).map(|i| i == 0).collect::<Vec<bool>>();
    for (a, b) in AB.into_iter() {
        v = update(v, a, b)
    }
    v[X]
}

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

アルゴリズムと数学 004

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

整数を3つではなく一般化しました。積にsumのようなものはないですが、foldが使えますね。

// Product of 3 Integers
#![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()
}


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

fn f(A: Vec<i32>) -> i32 {
    A.iter().fold(1, |x, y| x * y)
}

fn main() {
    let A: Vec<i32> = read_vec();
    println!("{}", f(A))
}

アルゴリズムと数学 003

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

VecはIteratorにするとsumが使えます。

// Sum of N Integers
#![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()
}


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

fn f(A: Vec<i32>) -> i32 {
    A.iter().sum::<i32>()
}

fn main() {
    let _N: usize = read();
    let A: Vec<i32> = read_vec();
    println!("{}", f(A))
}

アルゴリズムと数学 001

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

これから、アルゴリズムと数学 演習問題集を解いていきます。

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

// Print 5+N
#![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()
}


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

fn f(N: i32) -> i32 {
    5 + N
}

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