轻精灵在一个范围内寻找一个素数的所有乘法

Question

我想回答一个叫“小精灵”的问题。 给定一个小精灵的数组数和每个选择的素数，返回在所有小精灵切换到素数相乘后仍在启用范围内的数。你知道吗

给定输入：

30 3 2 3 5

输出：

15

这个箱子由一个30英尺长的走廊和三个小精灵组成。小精灵们的行动是 跟随： 第一个小精灵翻转开关{2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30}。所有这些 开关以前是关着的，所以现在是开着的。 第二个小精灵翻转开关{3, 6, 9, 12, 15, 18, 21, 24, 27, 30}。其中，{6, 12, 18, 24, 30} 以前是开的，所以现在是关的。这将导致以下开关打开：{2, 3, 4, 8, 9, 10, 14, 15, 16, 20, 21, 22, 26, 27, 28}。 第三个小精灵翻转开关{5, 10, 15, 20, 25, 30}。其中，{10, 15, 20}以前是打开的，所以 他们现在走了。这将导致以下开关打开：{2, 3, 4, 5, 8, 9, 14, 16, 21, 22, 25, 26, 27, 28, 30}。 因此，晚上有15个开关打开。你知道吗

现在我的代码非常直接：

testcases=int(input())
for i in range(0,testcases):
  array = input().split(' ')
  arrayofnumbers = [int(x) for x in array]
  #print(arrayofnumbers)
  onCount=0
  for j in range(1,arrayofnumbers[0]+1):
     primeCount=0
     for p in arrayofnumbers[2:len(arrayofnumbers)]:
        if j%p == 0:
            primeCount += 1
     if primeCount % 2 == 1:
         onCount += 1
print(onCount)

现在看来这对小数组或者我认为是可行的。我有一半的测试不及格，我真的不明白为什么。也许这不适用于非常大的阵列？也许我的整个方法都错了？你知道吗

我已经修改了我的代码以使用LCM并计算迭代的数量，但是这仍然没有解决其余的测试用例。这是我的密码：

from math import gcd

    testcases=int(input())
    for i in range(0,testcases):
      array = input().split(' ')
      arrayofnumbers = [int(x) for x in array]
      #print(arrayofnumbers)
      lcm = 1
      for i in arrayofnumbers[2:]:
          lcm = int(lcm * i / gcd(lcm, i))
      #print(lcm)

      if lcm >= arrayofnumbers[0]:
        onCount=0
        for j in range(1,arrayofnumbers[0]+1):
            primeCount=0
            for p in arrayofnumbers[2:len(arrayofnumbers)]:
                if j%p == 0:
                    primeCount += 1
            if primeCount % 2 == 1:
                 onCount += 1
        print(onCount)

      if lcm < arrayofnumbers[0]:
          numiters=int(arrayofnumbers[0]/lcm)
          onCount = 0
          extraonCount=0
          for j in range(1, lcm+1):
              primeCount = 0
              for p in arrayofnumbers[2:len(arrayofnumbers)]:
                  if j % p == 0:
                      primeCount += 1
              if primeCount % 2 == 1:
                  onCount += 1
          onCount = onCount * numiters

          for j in range(1, (arrayofnumbers[0]-(lcm*numiters))+1):
              primeCount = 0
              for p in arrayofnumbers[2:len(arrayofnumbers)]:
                  if j % p == 0:
                    primeCount += 1
              if primeCount % 2 == 1:
                extraonCount += 1
          onCount += extraonCount
        print(onCount)

使用一个不同的方法，使用一组可整除的数字，我没有得到任何测试用例超时，但错误的答案和一个更正确的测试用例，但仍然不是一个完全正确的答案。 利用这个想法： click link

testcases=int(input())
for i in range(0,testcases):
  array = input().split(' ')
  arrayofnumbers = [int(x) for x in array]
  arrayOfon = []
  arrayIterate = []
  arrayPrimes = []

  for j in arrayofnumbers[2:]:
      arrayPrimes.append(j)
  arrayPrimes.sort()

  print(arrayPrimes)

  for j in arrayPrimes:
      num=0
      num = int(arrayofnumbers[0] // j)
      arrayOfon.append(num)

  print(arrayOfon)

  for j in arrayPrimes[1:]:
      arrayIterate.append(j)


  print(arrayIterate)


  for j in range(0, len(arrayIterate)):
      x = 0
      y = 0
      y = arrayOfon[0]
      x = y // arrayIterate[j]
      arrayOfon[0] = (y - x) + (arrayOfon[j+1] - x)



  print(arrayOfon[0])

Answer 1

假设lcm是least common multiple，计数将重复每一个lcm数字，因此您不需要在整个范围内循环，只需计算在1..lcm范围内有多少开关打开，然后将其乘以int(n/lcm)（即序列将作为一个整体重复多少次），并将最后一项的计数相加，即从lcm*int*n/lcm)到结束。你知道吗

简单示例： 如果开关的数目是33，并且有两个小精灵：2和3，lcm(2,3)=6，那么您不需要从1一直计数到33，因为计数将每6个开关重复一次，并且将重复int(33/6)=5次。所以你只需要计算从1到6的开关数，再乘以5，再加上31到33的数值