1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

//!　数字、計算に関するメソッドを取り扱う

/// 比較可能な2つの引数のうち大きい方を返す
pub fn max<T: PartialOrd>(n: T, m: T) -> T {
    if n >= m {
        n
    } else {
        m
    }
}

/// 比較可能な2つの引数のうち小さい方を返す
pub fn min<T: PartialOrd>(n: T, m: T) -> T {
    if n <= m {
        n
    } else {
        m
    }
}

/// floor + as i64
pub fn into_floor(a: f64) -> i64 {
    a as i64
}

/// ceil + as i64
pub fn into_ceil(a: f64) -> i64 {
    if a % 1.0 == 0.0 {
        a as i64
    } else {
        a as i64 + 1
    }
}

/// `u64`の十進法での桁数
pub fn dight_scale(n: u64) -> u64 {
    if n == 0 {
        return 1;
    }
    let mut count = 0;
    let mut n = n;
    while n >= 1 {
        n /= 10;
        count += 1;
    }
    count
}

/// `u64`を桁ごとに`Vec<u64>`に分解
pub fn dight_vec(n: u64) -> Vec<u64> {
    let mut idx: u64 = dight_scale(n) - 1;
    let mut ret = Vec::new();
    loop {
        ret.push(n / pow_bin(10, idx) % 10u64);
        if idx == 0u64 {
            break;
        }
        idx -= 1;
    }
    ret
}

/// `u64`の十進法での各桁の和
pub fn dight_sum(n: u64) -> u64 {
    dight_vec(n).iter().sum()
}

/// 二分累乗法,
/// - `O(log n)`で累乗を求める
pub fn pow_bin(n: u64, r: u64) -> u64 {
    let mut res = 1u64;
    let mut a = n;
    let mut n = r;
    while n > 0 {
        if n & 1 != 0 {
            res *= a
        }
        a *= a;
        n >>= 1;
    }
    res
}

/// 互除法を用いて最大公約数を求める
pub fn gcd(n: u64, m: u64) -> u64 {
    let (mut n, mut m) = (max(n, m), min(n, m));
    if m == 0 {
        return n;
    }
    let mut _r = 0;
    while n % m != 0 {
        _r = n % m;
        n = m;
        m = _r;
    }
    m
}

/// 最小公倍数を求める
pub fn lcm(n: u64, m: u64) -> u64 {
    n * m / gcd(n, m)
}

/// 配列全体の最大公約数
pub fn gcd_vec(v: &[u64]) -> u64 {
    let mut r = v[0];
    for i in v.iter().skip(1) {
        r = gcd(r, *i);
    }
    r
}

/// 配列全体の最小公倍数
pub fn lcm_vec(v: &[u64]) -> u64 {
    let mut r = v[0];
    for i in v.iter().skip(1) {
        r = lcm(r, *i);
    }
    r
}

/// Find the first factor (other than 1) of a number
fn firstfac(x: u64) -> u64 {
    if x % 2 == 0 {
        return 2;
    };
    // TODO: return to step_by
    // for n in (3..).step_by(2).take_while(|m| m*m <= x) {
    for n in (3..).step_by(2).take_while(|m| m * m <= x) {
        if x % n == 0 {
            return n;
        };
    }
    // No factor found. It must be prime.
    x
}

/// Test whether a number is prime. Checks every odd number up to `sqrt(n)`.
pub fn is_prime(n: u64) -> bool {
    if n <= 1 {
        return false;
    }
    firstfac(n) == n
}