Rust テンプレート

programming

自分用

Rust勉強中

まだCっぽい書き方しかできない

入力

1行標準入力

fn readline() -> String {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    buf.trim_end()
}

ファイル入力

use std::io::{BufRead, BufReader};
use std::fs::File;

fn main() {
    let reader = BufReader::new(File::open("file.txt").unwrap());
    for line in reader.lines() {
        let buf = line.unwrap();
    }
}

素数

素数判定

TODO: AKS素数判定法を理解・実装

fn is_prime(n: usize) -> bool {
    if n <= 3 {
        return n > 1;
    } else if n % 2 == 0 || n % 3 == 0 {
        return false;
    }
    let mut i = 5;
    while i * i <= n {
        if n % i == 0 || n % (i + 2) == 0 {
            return false;
        }
        i += 6;
    }
    true
}

エラトステネスのふるい

そのまんま

// All the elements of `is_prime` must be initialized to true
// prior to calling this function.
fn sieve(is_prime: &mut [bool]) {
    is_prime[0] = false;
    is_prime[1] = false;
    let n = is_prime.len();
    let mut i = 2;
    while i * i <= n {
        if is_prime[i] {
            for j in (i * i..n).step_by(i) {
                is_prime[j] = false;
            }
        }
        i += 1;
    }
}

数

反転

fn reverse_num(mut n: usize) -> usize {
    let mut r = 0;
    while n > 0 {
        r *= 10;
        r += n % 10;
        n /= 10;
    }
    r
}

桁分解

fn digits_vec(mut n: usize, base: usize) -> Vec<usize> {
    let mut digits = vec![];
    while n > 0 {
        digits.push(n % base);
        n /= base;
    }
    digits.into_iter().rev().collect()
}

最大公約数と最小公倍数

fn gcd(mut a: usize, mut b: usize) -> usize {
    if a < b {
        std::mem::swap(&mut a, &mut b);
    }
    while b != 0 {
        let tmp = a;
        a = b;
        b = tmp % b;
    }
    a
}

fn lcm(a: usize, b: usize) -> usize {
    a / gcd(a, b) * b
}

約数の和

TODO: bを消す？(もっと簡単にできる？)

proper divisors(日本語でなんと言うか知らず)の和も載せとく

fn sum_of_divisors(n: usize) -> usize {
    if n == 0 {
        return 0;
    } else if n == 1 {
        return 1;
    }
    let mut sum = n + 1;
    let mut a = 2;
    let mut b = n;
    while a < b {
        if n % a == 0 {
            b = n / a;
            sum += if a == b { a } else { a + b };
        }
        a += 1;
    }
    sum
}

fn sum_of_proper_divisors(n: usize) -> usize {
    sum_of_divisors(n) - n
}

多倍長整数

num を使う

Cargo.toml

[package]
name = "problem_0xxx"
version = "0.1.0"

[dependencies]
num-bigint = "0.2"
num-traits = "0.2"

ソースコード

extern crate num_bigint;
extern crate num_traits;

use num_bigint::BigUint;
use num_traits::{pow, Zero, One};

fn main() {
}

階乗

このまま使うことはないだろうけど

fn fac(n: usize) -> BigUint {
    let mut r: BigUint = One::one();
    for i in 2..=n {
        r *= i;
    }
    r
}

フィボナッチ数

同じく

fn fib(n: usize) -> BigUint {
    if n == 0 {
        return Zero::zero();
    }
    let mut pre = Zero::zero();
    let mut cur = One::one();
    for i in 0..n {
        let next = &pre + &cur;
        pre = cur;
        cur = next;
    }
    cur
}

その他

next_permutation

stableにはこれ系がない

Next lexicographical permutation algorithm

ツェラーの公式

使うのか？

fn zeller(mut y: i32, mut m: i32, d: i32) -> i32 {
    let c = y / 100;
    let g = 5 * c + c / 4;
    if m == 1 || m == 2 {
        m += 12;
        y -= 1;
    }
    y %= 100;
    (d + 26 * (m + 1) / 10 + y + y / 4 + g) % 7
}

やっとLevel 1になった