Python程序：查找N个自然数中和能被k整除的数对数量

假设我们有一个数字n和另一个值k，考虑我们有一个数组A，其中包含前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])
• 返回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))

输入

4, 27

输出

10

Arnab Chakraborty

更新于： 2021年10月25日

213 次查看

开启您的 职业生涯

通过完成课程获得认证

开始学习