2022-06-19：给出n个数字，你可以任选其中一些数字相乘，相乘之后得到的新数字x，x的价值是x的不同质因子的数量。返回所有

use rand::Rng;
use std::collections::HashMap;
fn main() {
    let n: isize = 10;
    let v: isize = 20;
    let test_time: i32 = 5000;
    println!("测试开始");
    for _i in 0..test_time {
        let mut arr = random_array(n, v);
        let ans1 = sum_of_values1(&mut arr);
        let ans2 = sum_of_values2(&mut arr);
        if ans1 != ans2 {
            println!("出错了!");
            for num in &arr {
                print!("{} ", num);
            }
            println!("");
            println!("ans1 = {}", ans1);
            println!("ans2 = {}", ans2);
            break;
        }
    }
    println!("测试结束");
}

// 工具！
// 返回num质数因子列表(去重)
// 时间复杂度，根号(num)
fn primes(mut num: isize) -> Vec<isize> {
    let mut ans: Vec<isize> = vec![];
    let mut i: isize = 2;
    while i * i <= num && num > 1 {
        if num % i == 0 {
            ans.push(i);
            while num % i == 0 {
                num /= i;
            }
        }
        i += 1;
    }
    if num != 1 {
        ans.push(num);
    }
    return ans;
}

fn sum_of_values1(arr: &mut Vec<isize>) -> isize {
    return process1(arr, 0, 1);
}

fn process1(arr: &mut Vec<isize>, index: isize, pre: isize) -> isize {
    if index == arr.len() as isize {
        return primes(pre).len() as isize;
    }
    let p1 = process1(arr, index + 1, pre);
    let p2 = process1(arr, index + 1, pre * arr[index as usize]);
    return p1 + p2;
}

fn sum_of_values2(arr: &mut Vec<isize>) -> isize {
    // key : 某个质数因子
    // value : 有多少个数含有这个因子
    let mut cnt_map: HashMap<isize, isize> = HashMap::new();
    for num in arr.iter() {
        for factor in primes(*num).iter() {
            cnt_map.insert(
                *factor,
                if cnt_map.contains_key(factor) {
                    *cnt_map.get(factor).unwrap()
                } else {
                    0
                } + 1,
            );
        }
    }
    let n = arr.len() as isize;
    let mut ans = 0;
    // count ：含有这个因子的数，有多少个
    // others : 不含有这个因子的数，有多少个
    for (_, count) in cnt_map.iter() {
        let others = n - count;
        ans += (power(2, *count) - 1) * power(2, others);
    }
    return ans;
}

fn power(mut num: isize, mut n: isize) -> isize {
    if n == 0 {
        return 1;
    }
    let mut ans = 1;
    while n > 0 {
        if (n & 1) != 0 {
            ans *= num;
        }
        num *= num;
        n >>= 1;
    }
    return ans;
}

// 为了测试
fn random_array(n: isize, v: isize) -> Vec<isize> {
    let mut arr: Vec<isize> = vec![];
    for _i in 0..n {
        arr.push(rand::thread_rng().gen_range(0, v) + 1);
    }
    return arr;
}