Pythonで数の2乗が2つの数の積に等しい方法の数を見つけるプログラム

2つの配列nums1とnums2があるとすると、これら2つのルールに従って形成されたトリプレット（タイプ1とタイプ2）を見つける必要があります-

• トリプレット（i、j、k）if nums1 [i] ^ 2 =nums2 [j] * nums2 [k]ここで、[0 <=i
• トリプレット（i、j、k）if nums2 [i] ^ 2 =nums1 [j] * nums1 [k]ここで、[0 <=i

したがって、入力がnums1 =[7,4] nums2 =[5,2,8,9]のようである場合、タイプ1（1,1,2）、nums1のトリプレットがあるため、出力は1になります。 [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
    • tmp：=tmp +（存在する場合はarr2 [m]、それ以外の場合は0）*（存在する場合はarr2 [sq / mの商]、それ以外の場合は0）

例

理解を深めるために、次の実装を見てみましょう-

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

入力

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

出力

2