用 Python 编写程序，找出数字平方等于两个数字乘积的方法数

pythonserver side programmingprogramming更新于 2025/11/26 9:48:17

假设我们有两个数组 nums1 和 nums2，我们必须找到遵循这两个规则形成的三元组(类型 1 和类型 2)−

三元组 (i, j, k) 如果 nums1[i]^2 = nums2[j] * nums2[k] 其中 [0 <= i < nums1 的大小和 0 <= j < k < nums2 的大小]。
三元组 (i, j, k) 如果 nums2[i]^2 = nums1[j] * nums1[k] 其中 [0 <= i < nums2 的大小和 0 <= j < k < nums1 的大小]。

因此，如果输入为 nums1 = [7,4] nums2 = [5,2,8,9]，则输出将为 1，因为存在类型 1 的三元组，(1,1,2)，nums1[1]^2 = nums2[1] * nums2[2] = (16 = 2*8)。

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

cnt1 := 一个用于保存每个元素及其 nums1 计数的映射
cnt2 := 一个用于保存每个元素及其 nums2 计数的映射
定义一个函数 triplets() 。这将需要 arr1、arr2
ans := 0
对于 arr1 的 items() 中的每个 t、v，执行
- 如果存在，则 k := arr2[t]，否则为 0
- tmp := k*(k - 1) / 2
- sq := t * t
- 对于 arr2 中的每个 m，执行
  - 如果 m < t 且 sq mod m 与 0 相同，则
    - tmp := tmp + (arr2[m] 如果存在，否则为 0) * (arr2[quotient of sq/m] 如果存在，否则为 0)
ans := ans + tmp * v
返回 ans
从 main 方法中，执行以下操作−
返回 triplets(cnt1, cnt2) + triplets(cnt2, cnt1)

示例

让我们看看下面的实现以便更好地理解 −

from collections import Counter
def solve(nums1, nums2):
   cnt1 = Counter(nums1)
   cnt2 = Counter(nums2)

   def triplets(arr1, arr2):
      ans = 0
      for t, v in arr1.items():
         k = arr2.get(t, 0)
         tmp = k * (k - 1) // 2
         sq = t * t
         for m in arr2:
            if m < t and sq % m == 0:
               tmp += arr2.get(m, 0) * arr2.get(sq // m, 0)
            ans += tmp * v
      return ans

   return triplets(cnt1, cnt2) + triplets(cnt2, cnt1)
nums1 = [7,4]
nums2 = [5,2,8,9]
print(solve(nums1, nums2))