import random

tests = [
  'd',
  'l',
  'G',
  'zero',
  'RUV',
  'UV',
  'VR',
  'Vd',
]
coverage = {t:0 for t in tests}

def bezout(R0,R1):
  # sage gcd and xgcd fail to return monic for, e.g., (2*x,0)
  if R0 == 0 and R1 == 0: return 0,0,0
  if R1 == 0:
    return R0/R0.leading_coefficient(),1/R0.leading_coefficient(),0
  if R0 == 0:
    return R1/R1.leading_coefficient(),0,1/R1.leading_coefficient()
  return xgcd(R0,R1)

def sanedeg(f):
  if f == 0: return -Infinity
  return f.degree()

for loop in range(50000):
  q = random.choice([2,3,5,7,11,13,17,19,23,29])
  k = GF(q)
  kx.<x> = k[]
  coeffs1 = randrange(50)
  coeffs2 = randrange(50)
  coeffs3 = randrange(50)
  h = kx(sum(k.random_element()*x^i for i in range(coeffs1)))
  if h[0] == 0: continue
  R0 = h*kx(sum(k.random_element()*x^i for i in range(coeffs2)))
  R1 = h*kx(sum(k.random_element()*x^i for i in range(coeffs3)))

  G,U,V = bezout(R0,R1)
  assert G == U*R0+V*R1

  R = [R0,R1]
  while R[-1] != 0:
    R += [R[-2] % R[-1]]
  r = len(R)-1
  assert R[r] == 0

  for i in range(1,r):
    assert R[i] != 0
    assert R[i+1] == R[i-1]%R[i]

  d = [sanedeg(Ri) for Ri in R]
  l = [Ri.leading_coefficient() for Ri in R]

  for i in range(1,r): assert d[i] > d[i+1]
  assert d[r] == -Infinity
  coverage['d'] += 1

  for i in range(1,r): assert l[i] != 0
  coverage['l'] += 1

  if l[r-1] != 0:
    assert G == R[r-1]/l[r-1]
    coverage['G'] += 1

  if l[r-1] == 0:
    assert R0 == 0
    assert R1 == 0
    assert G == 0
    assert r == 1
    coverage['zero'] += 1

  U = [kx(1),kx(0)]
  V = [kx(0),kx(1)]
  for i in range(1,r):
    U += [U[-2]-(R[i-1]//R[i])*U[-1]]
    V += [V[-2]-(R[i-1]//R[i])*V[-1]]

  assert U[0] == 1
  assert V[0] == 0
  assert U[1] == 0
  assert V[1] == 1
  for i in range(1,r):
    assert U[i+1] == U[i-1] - (R[i-1]//R[i])*U[i]
    assert V[i+1] == V[i-1] - (R[i-1]//R[i])*V[i]

  for i in range(r+1):
    assert R[i] == U[i]*R0+V[i]*R1
    coverage['RUV'] += 1

  for i in range(r):
    assert U[i]*V[i+1]-U[i+1]*V[i] == (-1)^i
    coverage['UV'] += 1

  for i in range(r):
    assert V[i+1]*R[i]-V[i]*R[i+1] == (-1)^i*R0
    coverage['VR'] += 1

  if d[0] > d[1]:
    for i in range(r):
      assert sanedeg(V[i+1]) == d[0] - d[i]
      coverage['Vd'] += 1

for t in tests:
  print coverage[t],t