2022-07-27：小红拿到了一个长度为N的数组arr，她准备只进行一次修改， 可以将数组中任意一个

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代码