Untuk diberikan dua bilangan bulat A dan B, temukan sepasang angka X dan Y sedemikian sehingga A = X * Y dan B = X xor Y

Saya berjuang dengan masalah ini yang saya temukan di buku pemrograman kompetitif, tetapi tanpa solusi bagaimana melakukannya.

Untuk diberikan dua bilangan bulat A dan B (dapat ditampung dalam tipe bilangan bulat 64-bit), di mana A ganjil, temukan sepasang angka X dan Y sedemikian sehingga A = X * Y dan B = X xor Y. Pendekatan saya adalah mencantumkan semua pembagi dari A dan mencoba memasangkan angka di bawah sqrt (A) dengan angka lebih sqrt (A) yang multiply hingga A dan melihat apakah xor mereka adalah sama dengan B . Tetapi saya tidak tahu apakah itu cukup efisien. Apa solusi / algoritma yang baik untuk masalah ini?

Berikut adalah rekursi sederhana yang mengamati aturan yang kita tahu: (1) bit paling tidak signifikan dari kedua X dan Y ditetapkan karena hanya multiplicand ganjil menghasilkan kelipatan ganjil; (2) jika kita menetapkan X untuk memiliki bit set B tertinggi, Y tidak boleh lebih besar dari sqrt (A); dan (3) mengatur bit dalam X atau Y sesuai dengan bit saat ini di B.

Kode Python berikut menghasilkan di bawah 300 iterasi untuk semua kecuali satu pasangan acak yang saya ambil dari kode contoh Matt Timmermans . Tapi yang pertama mengambil 231.199 iterasi :)

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

Keluaran:

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

Anda tahu bahwa setidaknya satu faktor adalah <= sqrt (A). Mari kita buat yang X.

Panjang X dalam bit akan menjadi sekitar setengah panjang A.

Bit atas X, oleh karena itu - yang nilainya lebih tinggi dari sqrt (A) - semuanya 0, dan bit yang sesuai dalam B harus memiliki nilai yang sama dengan bit yang sesuai di Y.

Mengetahui bit bagian atas Y memberi Anda kisaran yang cukup kecil untuk faktor yang sesuai X = A / Y. Hitung Xmin dan Xmax masing-masing sesuai dengan nilai terbesar dan terkecil yang mungkin untuk Y. Ingat bahwa Xmax juga harus <= sqrt (A).

Kemudian coba saja semua Xs yang mungkin antara Xmin dan Xmax. Tidak akan terlalu banyak, jadi tidak akan lama.

Cara mudah lainnya untuk menyelesaikan masalah ini bergantung pada kenyataan bahwa n bit XY dan X xor Y yang lebih rendah hanya bergantung pada n bit X dan Y yang lebih rendah. Oleh karena itu, Anda dapat menggunakan jawaban yang mungkin untuk n bit yang lebih rendah untuk membatasi jawaban yang mungkin untuk n + 1 bit yang lebih rendah , sampai Anda selesai.

Saya telah menemukan bahwa, sayangnya, mungkin ada lebih dari satu kemungkinan untuk satu n . Saya tidak tahu seberapa sering akan ada banyak kemungkinan, tetapi mungkin tidak terlalu sering sama sekali, jadi ini mungkin baik-baik saja dalam konteks kompetitif. Secara probabilitas, hanya akan ada beberapa kemungkinan, karena solusi untuk n bit akan memberikan 0 atau dua solusi untuk n + 1 bit, dengan probabilitas yang sama.

Tampaknya bekerja dengan cukup baik untuk input acak. Berikut kode yang saya gunakan untuk mengujinya:

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

Anda dapat melihat hasilnya di sini: https://ideone.com/cEuHkQ

Sepertinya biasanya hanya butuh beberapa ribu cek.