Pythonで合計が1である分数ペアの数をカウントするプログラム

各分数が数（分子/分母）を表す個々のリスト[分子、分母]である分数のリストがあるとします。合計が1である分数のペアの数を見つける必要があります。

したがって、入力が分数=[[2、7]、[3、12]、[4、14]、[5、7]、[3、4]、[1、4]]のような場合、出力は（2/7 + 5/7）、（3/12 + 3/4）、（3/4 + 1/4）、（4/14 + 5/7）は合計する4つのペアであるため、4になります1に。

これを解決するには、次の手順に従います。

• d：=新しい地図
• ans：=0
• 分数の各分数iについて、実行します
  • x：=i[分子]
  • y：=i[分母]
  • g：=（x、y）のgcd
  • x：=x / g
  • y：=y / g
  • temp_x：=y-x
  • temp_y：=y
  • （temp_x、temp_y）がdにある場合、
    • ans：=ans + d [temp_x、temp_y]
  • d [x、y]：=1 +（d [（x、y）]が利用可能な場合、それ以外の場合は0）
• 回答を返す

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

サンプルコード

class Solution:
   def solve(self, fractions):
   import math

   d = {}
   ans = 0
   for i in fractions:
      x = i[0]
      y = i[1]
      g = math.gcd(x, y)
      x /= g
      y /= g
      temp_x = y - x
      temp_y = y
      if (temp_x, temp_y) in d:
         ans += d[(temp_x, temp_y)]
         d[(x, y)] = d.get((x, y), 0) + 1
      return ans

ob = Solution()
fractions = [[2, 7],[3, 12],[4, 14],[5, 7],[3, 4],[1, 4]]
print(ob.solve(fractions))

入力

[[2, 7],[3, 12],[4, 14],[5, 7],[3, 4],[1, 4]]

出力

4