2023-01-02：某天，小美在玩一款游戏，游戏开始时，有 n 台机器， 每台机器都有一个能量水平，分别为 a1、a2、…、an， 小美每次操作可以选其中的一台机器，假设选的是第 i 台， 那小美可以将其变成

use std::iter::repeat;fn main() {    let n = 5;    let m = 11;    let mut arr = vec![1, 3, 5, 7, 9];    let ans = times(n, m, &mut arr);    println!("ans = {:?}", ans);}
fn times(n: i32, m: i32, arr: &mut Vec<i32>) -> Vec<i32> {    // map[i] : i这个余数变成余数0，需要至少操作几次？    let mut map: Vec<i32> = repeat(0).take(m as usize).collect();    bfs(m, &mut map);    let mut ans: Vec<i32> = repeat(0).take(n as usize).collect();    for i in 0..n {        let num = arr[i as usize];        let mut min_times = i32::MAX;        if num < m {            min_times = map[num as usize];        } else {            let mut add: i64 = 1;            while add <= 1000000000 {                let mod0: i32 = ((num as i64 + add) % m as i64) as i32;                min_times = get_min(min_times, map[mod0 as usize] + 1);                add *= 10;            }        }        ans[i as usize] = min_times;    }    return ans;}
fn bfs(m: i32, map: &mut Vec<i32>) {    let mut visited: Vec<bool> = repeat(false).take(m as usize).collect();    visited[0] = true;    let mut queue: Vec<i32> = repeat(0).take(m as usize).collect();    let mut l = 0;    let mut r = 1;    // map[0] == 0    // 表示余数0变成余数0，需要至少0次    // 0进队列了, queue[0] = 0    // 0算访问过了，visited[0] = true    while l < r {        // 当前弹出的余数是cur        let cur = queue[l as usize];        l += 1;        // 能加的数字，从1枚举到10^9        let mut add: i64 = 1;        while add <= 1000000000 {            // 比如，m == 7            // 当前余数是cur，cur变成余数0，至少要a次            // 我们想知道 : (哪个余数b + add) % m == cur            // 比如,add=10的时候，cur==5的时候            // 我们想知道 : (哪个余数b + 10) % 7 == 5            // 因为10 % 7 = 3            // 所以其实我们在求 : 哪个余数b + 3 == 5            // 显然b = 5 - 3 = cur - (add % m) = 2            // 再比如，add=10的时候，cur==2的时候            // 我们想知道 : (哪个余数b + 10) % 7 == 2            // 因为10 % 7 = 3            // 所以其实我们在求 : 哪个余数b + 3 == 2            // 这明显是不对的，            // 所以其实我们在求 : 哪个余数b + 3 == 2 + m == 9            // 也就是b，通过加了add % m，来到了m + cur，多转了一圈            // b = 9 - 3 = cur - (add % m) + m = 6            // 也就是说，b = cur - (add % m)，            // 如果不小于0，那就是这个b，是我们要找的余数            // 如果小于0，那就是b+m，是我们要找的余数            let mut from: i32 = cur - (add % m as i64) as i32;            if from < 0 {                from += m;            }            // 这个余数我们终于找到了，因为cur变成余数0，需要a次            // 所以这个余数变成余数0，需要a+1次            // 当然前提是这个余数，之前宽度优先遍历的时候，没遇到过            if !visited[from as usize] {                visited[from as usize] = true;                map[from as usize] = map[cur as usize] + 1;                queue[r as usize] = from;                r += 1;            }            add *= 10;        }    }}
fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {    if a < b {        a    } else {        b    }}

// SPDX-License-Identifier: MITpragma solidity ^0.8.17;
contract Hello{    function main() public pure returns (int32[] memory){        int32 n = 5;        int32 m = 11;        int32[] memory arr = new int32[](5);        arr[0] = 1;        arr[1] = 3;        arr[2] = 5;        arr[3] = 7;        arr[4] = 9;        int32[] memory ans = times(n,m,arr);        return ans;    }
    function times(int32 n,int32 m,int32[] memory arr) public pure returns (int32[] memory){    // map[i] : i这个余数变成余数0，需要至少操作几次？        uint mm=uint(uint32(m));        int32[] memory map  = new int32[](mm);    bfs(m, map);        uint nn=uint(uint32(n));        int32[] memory ans  = new int32[](nn);    for (uint i = 0; i < nn; i++) {      int32 num = arr[i];      int32 minTimes = 2147483647;      if (num < m) {        minTimes = map[uint(uint32(num))];      } else {        for (int64 add = 1; add <= 1000000000; add *= 10) {          int32 mod = int32((int64(num) + add) % int64(m));          minTimes = getMin(minTimes, map[uint(uint32(mod))] + 1);        }      }      ans[i] = minTimes;    }    return ans;    }
    function getMin(int32 a,int32 b) public pure returns (int32){        if(a<b){            return a;        }else{            return b;        }    }
    function bfs(int32 m,int32[] memory map) public pure{        uint mm=uint(uint32(m));        bool[] memory visited = new bool[](mm);        visited[0]=true;        int32[] memory queue  = new int32[](mm);        int32 l = 0;        int32 r = 1;        // map[0] == 0    // 表示余数0变成余数0，需要至少0次    // 0进队列了, queue[0] = 0    // 0算访问过了，visited[0] = true        while(l<r){      // 当前弹出的余数是cur            int32 cur = queue[uint(uint32(l))];            l++;      // 能加的数字，从1枚举到10^9            for(int64 add = 1;add<=1000000000;add*=10){        // 比如，m == 7        // 当前余数是cur，cur变成余数0，至少要a次        // 我们想知道 : (哪个余数b + add) % m == cur        // 比如,add=10的时候，cur==5的时候        // 我们想知道 : (哪个余数b + 10) % 7 == 5        // 因为10 % 7 = 3        // 所以其实我们在求 : 哪个余数b + 3 == 5        // 显然b = 5 - 3 = cur - (add % m) = 2        // 再比如，add=10的时候，cur==2的时候        // 我们想知道 : (哪个余数b + 10) % 7 == 2        // 因为10 % 7 = 3        // 所以其实我们在求 : 哪个余数b + 3 == 2        // 这明显是不对的，        // 所以其实我们在求 : 哪个余数b + 3 == 2 + m == 9        // 也就是b，通过加了add % m，来到了m + cur，多转了一圈        // b = 9 - 3 = cur - (add % m) + m = 6        // 也就是说，b = cur - (add % m)，        // 如果不小于0，那就是这个b，是我们要找的余数        // 如果小于0，那就是b+m，是我们要找的余数                int32 from = cur - int32(add%int64(m));        if (from < 0) {          from += m;        }        // 这个余数我们终于找到了，因为cur变成余数0，需要a次        // 所以这个余数变成余数0，需要a+1次        // 当然前提是这个余数，之前宽度优先遍历的时候，没遇到过        if (!visited[uint(uint32(from))]) {          visited[uint(uint32(from))] = true;          map[uint(uint32(from))] = map[uint(uint32(cur))] + 1;          queue[uint(uint32(r))] = from;                    r++;        }            }        }    }
}