2022-07-27：小红拿到了一个长度为N的数组arr，她准备只进行一次修改，
可以将数组中任意一个数arr[i]，修改为不大于P的正数（修改后的数必须和原数不同)，
并使得所有数之和为X的倍数。
小红想知道，一共有多少种不同的修改方案。
1 <= N, X <= 10^5。
1 <= arr[i], P <= 10^9。
来自网易。
答案2022-07-27：
求所有数字的累加和sum。遍历，sum-[i]求次数，最后统计次数。
这道题关键在于发现数学规律。
时间复杂度：O(N)。
代码用rust编写。代码如下：
use rand::Rng;
fn main() {
let len: i64 = 100;
let value: i64 = 100;
let test_time: i32 = 100000;
println!("测试开始");
for _ in 0..test_time {
let n = rand::thread_rng().gen_range(0, len) + 1;
let mut arr = random_array(n, value);
let p = rand::thread_rng().gen_range(0, value) + 1;
let x = rand::thread_rng().gen_range(0, value) + 1;
let ans1 = ways1(&mut arr, p, x);
let ans2 = ways2(&mut arr, p, x);
if ans1 != ans2 {
println!("出错了!");
break;
}
}
println!("测试结束");
}
fn ways1(arr: &mut Vec<i64>, p: i64, x: i64) -> i64 {
let mut sum = 0;
for num in arr.iter() {
sum += *num;
}
let mut ans = 0;
for num in arr.iter() {
sum -= *num;
for v in 1..=p {
if v != *num {
if (sum + v) % x == 0 {
ans += 1;
}
}
}
sum += num;
}
return ans;
}
fn ways2(arr: &mut Vec<i64>, p: i64, x: i64) -> i64 {
let mut sum = 0;
for num in arr.iter() {
sum += *num;
}
let mut ans = 0;
for num in arr.iter() {
ans += cnt(p, x, *num, (x - ((sum - *num) % x)) % x);
}
return ans;
}
// 当前数字num
// 1~p以内，不能是num的情况下，% x == mod的数字有几个
// O(1)
fn cnt(p: i64, x: i64, num: i64, mod0: i64) -> i64 {
// p/x 至少有几个
// (p % x) >= mod ? 1 : 0
// 在不考虑变出来的数，是不是num的情况下，算一下有几个数，符合要求
let ans = p / x + if (p % x) >= mod0 { 1 } else { 0 } - if mod0 == 0 { 1 } else { 0 };
// 不能等于num！
return ans - if num <= p && num % x == mod0 { 1 } else { 0 };
}
// 为了测试
fn random_array(n: i64, v: i64) -> Vec<i64> {
let mut ans: Vec<i64> = vec![];
for _ in 0..n {
ans.push(rand::thread_rng().gen_range(0, v) + 1);
}
return ans;
}
执行结果如下：
左神java代码
