给出n个数字，你可以任选其中一些数字相乘，相乘之后得到的新数字x，
x的价值是x的不同质因子的数量。
返回所有选择数字的方案中，得到的x的价值之和。
今晚在群里吹牛给耽误了，具体见代码。
代码用rust编写。代码如下：
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;
}执行结果如下：
