[PYTHON] Project Euler 33

problem

49/98 is an interesting fraction. An inexperienced mathematician mistakenly thinks, "If you remove 9 from each of the numerator and denominator, you get 49/98 = 4/8, which is a simple form." Maybe. (The method is incorrect, but in the case of 49/98 it happens to be the correct fraction.)

We assume that types like 30/50 = 3/5 are trivial examples.

Of these fractions, there are four that are less than one and are not trivial, with both the numerator and denominator being two-digit numbers.

Answer the value of the denominator when the product of the four fractions is given in the reduced form. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2033

Answer

Two fractions a1 / b1 and a2 / b2 have the same value →　a1//gcd(a1, b1) == a2//gcd(a2,b2) and b1//gcd(a1, b1) == b2//gcd(a2,b2) A fraction of a fraction a / b →　(a//gcd(a,b)) / (b//gcd(a,b))

I coded it appropriately based on the above facts. I want to fix it soon (= I won't do it)

def gcd(m,n):
  if m < n:
    (m,n) = (n,m)
  while n != 0:
    (m,n) = (n,m%n)
  return m
  
def main():
  seq = range(11,100)
  ans_x = 1
  ans_y = 1
  for i in seq:
    for j in seq[i+1:]:
      for (x, y) in delete_same_number(i,j):
        x, y = int(x), int(y)
        if x == 0 or y == 0:
          break

        gcd1 = gcd(i,j)
        gcd2 = gcd(x,y)
        if (i//gcd1 == x//gcd2) and (j//gcd1 == y//gcd2):
          if (i%10) == 0 or (j%10) == 0:
            pass
          else:
            ans_x *= x//gcd2
            ans_y *= y//gcd2
  print ans_y//gcd(ans_x,ans_y)

def delete_same_number(i,j):
  s1 = str(i)
  s2 = str(j)
  if s1[0] == s2[0]:
    yield (s1[1], s2[1])
  if s1[0] == s2[1]:
    yield (s1[1], s2[0])
  if s1[1] == s2[0]:
    yield (s1[0], s2[1])
  if s1[1] == s2[1]:
    yield (s1[0], s2[0])
  yield ('0','0')
main()