找出总和可被k整除的对数？

Question

给定k的值。这样k <= 100000我们必须打印对的数量，使得每对元素的总和可以被k整除。在以下条件下，第一个元素应小于第二个元素，并且两个元素应小于109。

Answer 1

我找到了一个解决方案，让a和b数字使得(a+b)%k=0然后我们必须找到对(a,b)，其中a<b，所以让我们计算有多少对(a,b)满足条件a+b=k，例如如果k=3 0+3=3, 1+2=3, 2+1=3, 3+0=3有4对但只有2对(K+1)/2 (integer division)如此相似找到对(a,b)，其中总和是2k, 3k,.. nk，解决方案将是(k+1)/2 + (2k+1)/2 + (3k+1)/2 + ... + (nk+1)/2，这等于(k*n*(n+1)/2 + n)/2与时间复杂度O(1)，如果n*k=2*10^9，因为a不能对于给定的约束，超过10^9。

Answer 2

一些伪代码可以帮助您入门。它使用你说你试过的蛮力技术，但你的代码可能有问题吗？

max = 1000000000
numberPairs = 0
for i = 1 to max - 2 do
    for j = i + 1 to max - 1 do
        if (i + j) mod k = 0 then
            numberPairs = numberPairs + 1
        end if
    end do
end do

Answer 3

一种方式是蛮力：

int numPairs = 0;
for (i = 0; i < 10e9; i++)
{
    for (j = i+1; j < 10e9; j++)
    {
        int sum = i + j;
        if (sum % k == 0) numPairs++;
    }
 }
 return numPairs;

我会留给你优化这个以获得性能。我至少可以想到一种方法来显着提高速度。