k的倍数用编程怎么弄

时间:2025-01-28 03:18:58 网络游戏

要使用编程方法找出数组中k的倍数,可以采用以下几种方法:

方法一:累加和法

计算累加和数组:

首先计算数组的前缀和,然后遍历累加和数组,对于每个元素`sum[i]`,检查`sum[i] - sum[j]`是否是k的倍数,其中`j`从0遍历到`i-1`。如果是,则`i - j`就是以第`j`个元素结尾的长度最长的子串的长度。

```java

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

while (in.hasNext()) {

int n = in.nextInt();

in.nextLine();

long[] sum = new long[n + 1];

sum = 0;

for (int i = 1; i <= n; i++) {

sum[i] = sum[i - 1] + in.nextLong();

}

int maxLength = 0;

for (int i = 1; i <= n; i++) {

for (int j = 0; j < i; j++) {

if ((sum[i] - sum[j]) % k == 0) {

maxLength = Math.max(maxLength, i - j);

}

}

}

System.out.println(maxLength);

}

in.close();

}

}

```

方法二:前缀和优化

计算前缀和数组:

同样计算数组的前缀和,但这次我们利用前缀和数组来快速计算任意子数组的和。

统计余数:

遍历前缀和数组,统计每个前缀和对k取模后的余数,并记录每个余数出现的次数。

组合数计算:

对于每个余数,计算其可以组成的k倍区间的数量,即从该余数开始到数组末尾的所有可能的子数组长度。

```java

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

while (in.hasNext()) {

int n = in.nextInt();

in.nextLine();

long[] sum = new long[n + 1];

sum = 0;

for (int i = 1; i <= n; i++) {

sum[i] = sum[i - 1] + in.nextLong();

}

int[] cnt = new int[k];

for (int i = 1; i <= n; i++) {

int remainder = (int) (sum[i] % k);

cnt[remainder]++;

}

long result = 0;

for (int i = 1; i < k; i++) {

result += (long) cnt[i] * (cnt[i] - 1) / 2;

}

result += cnt;

System.out.println(result);

}

in.close();

}

}

```

方法三:数学方法

前缀和优化:

与方法二类似,但这次我们直接利用前缀和数组来计算k倍区间的数量。

组合数计算:

通过数学方法计算组合数,得出k倍区间的总数。