cp_library_rs/utils/
palindrome.rs

1//! 回文数に関するユーティリティ
2
3use crate::utils::usize_pow::PowUsize;
4
5/// d 桁の自然数を昇順に出力するイテレータ
6/// - 時間計算量: O(10^d) (whole)
7pub fn generate_d_digit_number(d: usize) -> impl Iterator<Item = usize> {
8    if d == 0 {
9        0..1
10    } else {
11        10.pow(d - 1)..10.pow(d)
12    }
13}
14
15/// n を 10 進数で表したとき，桁を逆順に並べ替えた数を返す
16pub fn inverted_number(mut n: usize) -> usize {
17    let mut r = 0;
18    while n > 0 {
19        r = r * 10 + n % 10;
20        n /= 10;
21    }
22    r
23}
24
25/// N 以下の回文数を昇順に出力するイテレータ
26/// - 時間計算量: O(√N) (whole)
27pub fn generate_palindrome_number(N: usize) -> impl Iterator<Item = usize> {
28    let n_length = (N as f32).log10().ceil() as usize;
29
30    (0..=n_length / 2)
31        .flat_map(|d| {
32            (generate_d_digit_number(d).map(move |k| k * 10.pow(d) + inverted_number(k))).chain(
33                generate_d_digit_number(d).flat_map(move |k| {
34                    (0..=9).map(move |m| (k * 10 + m) * 10.pow(d) + inverted_number(k))
35                }),
36            )
37        })
38        // 最初の0は除外
39        .skip(1)
40        .take_while(move |k| k <= &N)
41}
42
43/// 自然数 `n` を `a` 進数とみなしたとき，回文数であるか判定する．
44/// - `a = 0` のとき panic する
45/// - `a = 1` のとき `true` を返す．
46pub fn is_palindrome(mut n: usize, a: usize) -> bool {
47    match a {
48        0 => panic!("Base cannot be 0"),
49        1 => return true,
50        _ => {}
51    }
52    let mut ps = vec![];
53    while n > 0 {
54        ps.push(n % a);
55        n /= a;
56    }
57    ps.iter()
58        .zip(ps.iter().rev())
59        .take(ps.len() / 2)
60        .all(|(x, y)| x == y)
61}
cp_library_rs/utils/palindrome.rs

cp_library_rs/utils/
palindrome.rs
