def cornacchia(a, b, m):
 sols = set()
 a1 = igcdex(a, m)[0]
 v = sqrt_mod(((- b) * a1), m, all_roots=True)
 if (not v):
  return None
 for t in v:
  if (t < (m // 2)):
   continue
  (u, r) = (t, m)
  while True:
   (u, r) = (r, (u % r))
   if ((a * (r ** 2)) < m):
    break
  m1 = (m - (a * (r ** 2)))
  if ((m1 % b) == 0):
   m1 = (m1 // b)
   (s, _exact) = integer_nthroot(m1, 2)
   if _exact:
    if ((a == b) and (r < s)):
     (r, s) = (s, r)
    sols.add((int(r), int(s)))
 return sols

def cornacchia ( a , b , m ) : sols = set ( ) a1 = igcdex ( a , m ) [ 0 ] v = sqrt_mod ( ( ( - b ) * a1 ) , m , all_roots = True ) if ( not v ) : return None for t in v : if ( t < ( m // 2 ) ) : continue ( u , r ) = ( t , m ) while True : ( u , r ) = ( r , ( u % r ) ) if ( ( a * ( r ** 2 ) ) < m ) : break m1 = ( m - ( a * ( r ** 2 ) ) ) if ( ( m1 % b ) == 0 ) : m1 = ( m1 // b ) ( s , _exact ) = integer_nthroot ( m1 , 2 ) if _exact : if ( ( a == b ) and ( r < s ) ) : ( r , s ) = ( s , r ) sols . add ( ( int ( r ) , int ( s ) ) ) return sols
solves ax^2 + by^2 = m where gcd = 1 = gcd and a .