Chương trình tìm số cách bình phương của số bằng tích của hai số trong Python

Giả sử chúng ta có hai mảng nums1 và nums2, chúng ta phải tìm các bộ ba được tạo thành (kiểu 1 và kiểu 2) tuân theo hai quy tắc sau -

• Bộ ba (i, j, k) nếu nums1 [i] ^ 2 =nums2 [j] * nums2 [k] trong đó [0 <=i
• Bộ ba (i, j, k) nếu nums2 [i] ^ 2 =nums1 [j] * nums1 [k] trong đó [0 <=i

Vì vậy, nếu đầu vào giống như nums1 =[7,4] nums2 =[5,2,8,9], thì đầu ra sẽ là 1 vì có một bộ ba kiểu 1, (1,1,2), nums1 [1] ^ 2 =nums2 [1] * nums2 [2] =(16 =2 * 8).

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:

• cnt1:=một bản đồ để chứa từng phần tử và số lượng nums1 của nó
• cnt2:=một bản đồ để chứa từng phần tử và số lượng nums2 của nó
• Xác định hàm bộ ba (). Điều này sẽ lấy arr1, arr2
• ans:=0
• đối với mỗi t, v trong các mục () của arr1, thực hiện
  • k:=arr2 [t] nếu nó ở đó, nếu không thì 0
  • tmp:=k * (k - 1) / 2
  • sq:=t * t
  • đối với mỗi m trong arr2, thực hiện
    • nếu m
    • tmp:=tmp + (arr2 [m] nếu nó ở đó, nếu không thì 0) * (arr2 [thương số của sq / m] nếu nó ở đó, nếu không thì 0)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn−

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))

Đầu vào

[7,4],[5,2,8,9]

Đầu ra

2