Para dos números enteros A y B, encuentre un par de números X e Y de manera que A = X * Y y B = X xo Y

Estoy luchando con este problema que encontré en un libro de programación competitivo, pero sin una solución, cómo hacerlo.

Para dos enteros dados A y B (pueden caber en el tipo de entero de 64 bits), donde A es impar, encuentre un par de números X e Y de manera que A = X * Y y B = X xo Y. Mi enfoque fue enumerar todos los divisores de a y tratan números de emparejamiento de bajo sqrt (a) con los números sobre sqrt (a) que se multiplican hasta a y ver si sus xor es igual a B . Pero no sé si eso es lo suficientemente eficiente. ¿Cuál sería una buena solución / algoritmo para este problema?

Aquí hay una recursión simple que observa las reglas que conocemos: (1) los bits menos significativos de X e Y se establecen ya que solo los multiplicandos impares producen un múltiplo impar; (2) si establecemos que X tenga el bit de ajuste más alto de B, Y no puede ser mayor que sqrt (A); y (3) establecer bits en X o Y de acuerdo con el bit actual en B.

El siguiente código de Python resultó en menos de 300 iteraciones para todos menos uno de los pares aleatorios que elegí del código de ejemplo de Matt Timmermans . Pero el primero tomó 231,199 iteraciones :)

from math import sqrt

def f(A, B):
  i = 64
  while not ((1<<i) & B):
    i = i - 1
  X = 1 | (1 << i)

  sqrtA = int(sqrt(A))

  j = 64
  while not ((1<<j) & sqrtA):
    j = j - 1

  if (j > i):
    i = j + 1

  memo = {"it": 0, "stop": False, "solution": []}

  def g(b, x, y):
    memo["it"] = memo["it"] + 1
    if memo["stop"]:
      return []

    if y > sqrtA or y * x > A:
      return []

    if b == 0:
      if x * y == A:
        memo["solution"].append((x, y))
        memo["stop"] = True
        return [(x, y)]
      else:
        return []

    bit = 1 << b

    if B & bit:
      return g(b - 1, x, y | bit) + g(b - 1, x | bit, y)
    else:
      return g(b - 1, x | bit, y | bit) + g(b - 1, x, y)

  g(i - 1, X, 1)
  return memo

vals = [
  (6872997084689100999, 2637233646), # 1048 checks with Matt's code
  (3461781732514363153, 262193934464), # 8756 checks with Matt's code
  (931590259044275343, 5343859294), # 4628 checks with Matt's code
  (2390503072583010999, 22219728382), # 5188 checks with Matt's code
  (412975927819062465, 9399702487040), # 8324 checks with Matt's code
  (9105477787064988985, 211755297373604352), # 3204 checks with Matt's code
  (4978113409908739575,67966612030), # 5232 checks with Matt's code
  (6175356111962773143,1264664368613886), # 3756 checks with Matt's code
  (648518352783802375, 6) # B smaller than sqrt(A)
]

for A, B in vals:
  memo = f(A, B)
  [(x, y)] = memo["solution"]
  print "x, y: %s, %s" % (x, y)
  print "A:   %s" % A
  print "x*y: %s" % (x * y)
  print "B:   %s" % B
  print "x^y: %s" % (x ^ y)
  print "%s iterations" % memo["it"]
  print ""

Salida:

x, y: 4251585939, 1616572541
A:   6872997084689100999
x*y: 6872997084689100999
B:   2637233646
x^y: 2637233646
231199 iterations

x, y: 262180735447, 13203799
A:   3461781732514363153
x*y: 3461781732514363153
B:   262193934464
x^y: 262193934464
73 iterations

x, y: 5171068311, 180154313
A:   931590259044275343
x*y: 931590259044275343
B:   5343859294
x^y: 5343859294
257 iterations

x, y: 22180179939, 107776541
A:   2390503072583010999
x*y: 2390503072583010999
B:   22219728382
x^y: 22219728382
67 iterations

x, y: 9399702465439, 43935
A:   412975927819062465
x*y: 412975927819062465
B:   9399702487040
x^y: 9399702487040
85 iterations

x, y: 211755297373604395, 43
A:   9105477787064988985
x*y: 9105477787064988985
B:   211755297373604352
x^y: 211755297373604352
113 iterations

x, y: 68039759325, 73164771
A:   4978113409908739575
x*y: 4978113409908739575
B:   67966612030
x^y: 67966612030
69 iterations

x, y: 1264664368618221, 4883
A:   6175356111962773143
x*y: 6175356111962773143
B:   1264664368613886
x^y: 1264664368613886
99 iterations

x, y: 805306375, 805306369
A:   648518352783802375
x*y: 648518352783802375
B:   6
x^y: 6
59 iterations

Usted sabe que al menos un factor es <= sqrt (A). Hagamos esa X.

La longitud de X en bits será aproximadamente la mitad de la longitud de A.

Los bits superiores de X, por lo tanto, los de mayor valor que sqrt (A), son todos 0, y los bits correspondientes en B deben tener el mismo valor que los bits correspondientes en Y.

Conocer los bits superiores de Y te da un rango bastante pequeño para el factor correspondiente X = A / Y. Calcule Xmin y Xmax correspondientes a los valores más grandes y más pequeños posibles para Y, respectivamente. Recuerde que Xmax también debe ser <= sqrt (A).

Luego prueba todas las X posibles entre Xmin y Xmax. No habrá demasiados, por lo que no llevará mucho tiempo.

La otra forma directa de resolver este problema se basa en el hecho de que los n bits más bajos de XY y X xor Y dependen solo de los n bits más bajos de X e Y. Por lo tanto, puede usar las posibles respuestas para los n bits más bajos para restringir las posibles respuestas para los n + 1 bits inferiores , hasta que haya terminado.

He deducido que, desafortunadamente, puede haber más de una posibilidad para una sola n . No sé con qué frecuencia habrá muchas posibilidades, pero probablemente no lo sea con demasiada frecuencia, por lo que esto puede estar bien en un contexto competitivo. Probablemente, solo habrá unas pocas posibilidades, ya que una solución para n bits proporcionará 0 o dos soluciones para n + 1 bits, con la misma probabilidad.

Parece funcionar bastante bien para la entrada aleatoria. Aquí está el código que usé para probarlo:

public static void solve(long A, long B)
{
    List<Long> sols = new ArrayList<>();
    List<Long> prevSols = new ArrayList<>();
    sols.add(0L);
    long tests=0;
    System.out.print("Solving "+A+","+B+"... ");
    for (long bit=1; (A/bit)>=bit; bit<<=1)
    {
        tests += sols.size();
        {
            List<Long> t = prevSols;
            prevSols = sols;
            sols = t;
        }
        final long mask = bit|(bit-1);
        sols.clear();
        for (long prevx : prevSols)
        {
            long prevy = (prevx^B) & mask;
            if ((((prevx*prevy)^A)&mask) == 0)
            {
                sols.add(prevx);
            }
            long x = prevx | bit;
            long y = (x^B)&mask;
            if ((((x*y)^A)&mask) == 0)
            {
                sols.add(x);
            }
        }
    }
    tests += sols.size();
    {
        List<Long> t = prevSols;
        prevSols = sols;
        sols = t;
    }
    sols.clear();
    for (long testx: prevSols)
    {
        if (A/testx >= testx)
        {
            long testy = B^testx;
            if (testx * testy == A)
            {
                sols.add(testx);
            }
        }
    }

    System.out.println("" + tests + " checks -> X=" + sols);
}
public static void main(String[] args)
{
    Random rand = new Random();
    for (int range=Integer.MAX_VALUE; range > 32; range -= (range>>5))
    {
        long A = rand.nextLong() & Long.MAX_VALUE;
        long X = (rand.nextInt(range)) + 2L;
        X|=1;
        long Y = A/X;
        if (Y==0)
        {
            Y = rand.nextInt(65536);
        }
        Y|=1;
        solve(X*Y, X^Y);
    }
}

Puede ver los resultados aquí: https://ideone.com/cEuHkQ

Parece que generalmente solo toma un par de miles de cheques.