使用Python查找N个自然数中其和可被K整除的数字对的程序

假设我们有数字n和另一个值k，考虑一个具有前N个自然数的数组A，我们必须找到元素A [i]和A [j]的总数对，使得i ＜j并且它们的和可被k整除。

因此，如果输入如n = 10，k = 4，则输出将为10，因为有10对数的和可被4整除。[(1,3)，（1,7），（2,6），（2,10），（3,5），（3,9），（4,8），（5,7），（6,10），（7,9）]

为了解决这个问题，我们将遵循以下步骤：

m：=正向（n / k），r：= n mod k
b：=新映射
对于i在0到k-1之间的范围内
- b [i]：= m
对于i在m * k + 1到n之间的范围内进行
- j：= i mod k
- b [j]：= b [j] + 1
c：= 0
对于i在0到k之间的范围内
- i1：= i
- i2：= (k-i) mod k
- 如果i1与i2相同，则
  - c：= c + b [i] *（b [i] – 1）
- 否则，
  - c：= c + b [i1] *（b [i2]）
返回floor c / 2

示例

让我们看以下实现以便更好地了解-

def solve(n, k):
   m = n // k
   r = n % k

   b = {}
   for i in range(k) :
      b[i] = m
   for i in range(m*k+1, n+1) :
      j = i % k
      b[j] = b[j] + 1

   c = 0
   for i in range(k) :
      i1 = i
      i2 = (k - i) % k
      if i1 == i2 :
         c = c + b[i] * (b[i]-1)
      else :
         c = c + b[i1] * (b[i2])
   return c//2

n = 10
k = 4
print(solve(n, k))