Finden Sie für gegebene zwei ganze Zahlen A und B ein Paar von Zahlen X und Y, so dass A = X * Y und B = X x oder Y.

Ich habe mit diesem Problem zu kämpfen, das ich in einem wettbewerbsfähigen Programmierbuch gefunden habe, aber ohne eine Lösung, wie es geht. Suchen

Sie für zwei gegebene ganze Zahlen A und B (kann in einen 64-Bit-Integer-Typ passen), wobei A ungerade ist, ein Paar von Zahlen X und Y, so dass A = X * Y und B = X x oder Y. Mein Ansatz war es, aufzulisten alle Teiler von A und versuchen, Zahlen unter sqrt (A) mit Zahlen über sqrt (A) zu paaren, die sich mit A multiplizieren und prüfen, ob ihr xor gleich B ist . Aber ich weiß nicht, ob das effizient genug ist. Was wäre eine gute Lösung / ein guter Algorithmus für dieses Problem?

Hier ist eine einfache Rekursion, die die uns bekannten Regeln beachtet: (1) Die niedrigstwertigen Bits von X und Y werden gesetzt, da nur ungerade Multiplikanden ein ungerades Vielfaches ergeben. (2) wenn wir X so einstellen, dass es das höchste gesetzte Bit von B hat, kann Y nicht größer als sqrt (A) sein; und (3) Setzen von Bits in X oder Y gemäß dem aktuellen Bit in B.

Der folgende Python-Code führte zu weniger als 300 Iterationen für alle bis auf eines der zufälligen Paare, die ich aus Matt Timmermans Beispielcode ausgewählt habe . Aber der erste dauerte 231.199 Iterationen :)

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 ""

Ausgabe:

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

Sie wissen, dass mindestens ein Faktor <= sqrt (A) ist. Machen wir das eine X.

Die Länge von X in Bits beträgt ungefähr die Hälfte der Länge von A.

Die oberen Bits von X - diejenigen mit einem höheren Wert als sqrt (A) - sind daher alle 0, und die entsprechenden Bits in B müssen denselben Wert haben wie die entsprechenden Bits in Y.

Wenn Sie die oberen Bits von Y kennen, erhalten Sie einen ziemlich kleinen Bereich für den entsprechenden Faktor X = A / Y. Berechnen Sie Xmin und Xmax entsprechend den größtmöglichen und kleinstmöglichen Werten für Y. Denken Sie daran, dass Xmax auch <= sqrt (A) sein muss.

Dann probieren Sie einfach alle möglichen Xs zwischen Xmin und Xmax aus. Es wird nicht zu viele geben, also wird es nicht sehr lange dauern.

Der andere einfache Weg, um dieses Problem zu lösen, beruht auf der Tatsache, dass die unteren n Bits von XY und X x oder Y nur von den unteren n Bits von X und Y abhängen. Daher können Sie die möglichen Antworten für die unteren n Bits zur Einschränkung verwenden die möglichen Antworten für die unteren n + 1 Bits, bis Sie fertig sind.

Ich habe herausgefunden, dass es leider mehr als eine Möglichkeit für ein einzelnes n geben kann . Ich weiß nicht, wie oft es viele Möglichkeiten geben wird, aber es ist wahrscheinlich nicht zu oft, wenn überhaupt, so dass dies in einem Wettbewerbskontext in Ordnung sein kann. Wahrscheinlich gibt es nur wenige Möglichkeiten, da eine Lösung für n Bits mit gleicher Wahrscheinlichkeit entweder 0 oder zwei Lösungen für n + 1 Bits liefert .

Es scheint ziemlich gut für zufällige Eingaben zu funktionieren. Hier ist der Code, mit dem ich ihn getestet habe:

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);
    }
}

Sie können die Ergebnisse hier sehen: https://ideone.com/cEuHkQ

Sieht so aus, als würde es normalerweise nur ein paar tausend Schecks dauern.