-2

假设，我有一组N(N<=10^10) 自然数。其中，我想形成 2 个数字的集合，使得它们的总和可以被 整除k。假设，N=4即，数字：1, 2, 3, 4和k=2。因此，形成的集合将是::(1,3)和(2,4)。

没有重复，并且集合的第一个元素应该小于第二个元素。

以下是我的代码和逻辑。但我不知道为什么它对 N 的 lage 值给出不正确的答案：

int c[] = new int[K];
for (long j=1;j<=N;j++) {
    ++c[(int)j%K];//storing remainder in array
}
long count = 0; 
if (K%2==0)
    count = (c[0]*(c[0]-1) + c[K/2]*(c[K/2]-1))/2;//modulus that have value 0 or half of k, should be paired together, in C(N,2) ways.
else
    count = c[0]*(c[0]-1)/2;
for (int j=1;j<(K+1)/2;j++) {
    count+=c[j]*c[K-j];//sets whose modulus form a sum of K
}
4

1 回答 1

1

我至少看到两件事：

首先，在这一行：

++c[(int)j%K];//storing remainder in array

我很确定它会int在实际执行%操作之前进行强制转换（但不是 100% 肯定）。

其次，在其余代码中，对于所有count = ...行，您都在对ints 进行算术运算，然后将结果分配给 a long。long直到算术运算完成后才会执行隐式转换。因此，如果操作溢出 an int，您最终会溢出然后强制转换为 a long。

如果要解决此问题，则必须long在右侧显式地进行强制转换，以确保没有任何算术运算在两个ints 上进行。（虽然除非你有内存限制，最好在long任何地方都使用 s 而不是ints，除了jand K）

于 2013-09-12T00:48:29.720 回答