您知道至少一个因素是

以位为单位的X的长度大约是A的一半。

因此，X的高位-值比sqrt（A）高-全为0，并且B中的对应位必须与Y中的对应位具有相同的值。

知道Y的高位时，对应因数X = A / Y的范围很小。计算Xmin和Xmax分别对应于Y的最大和最小可能值。请记住，Xmax也必须为

然后只需尝试Xmin和Xmax之间的所有可能的X。不会太多，因此不会花费很长时间。

解决此问题的另一种直接方法取决于以下事实：XY和X的低 n 位x或Y仅取决于X和X的低 n 位是。因此，您可以使用 n 较低位的可能答案来限制 n + 1 较低位的可能答案，直到完成。 >

不幸的是，我得出一个 n 可能有不止一种可能性。我不知道有多少种可能性，但是如果可能的话，这种可能性可能不太常见，因此在竞争环境中这可能很好。概率上，只有少数可能性，因为 n 位的解决方案将以相等的概率为0 n + 1 位提供0或两个解决方案。

对于随机输入来说，效果似乎很好。这是我用来测试的代码：

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

您可以在此处查看结果：https://ideone.com/cEuHkQ

看起来通常只需要几千张支票。

这里有一个简单的递归，它遵循我们知道的规则：（1）X和Y的最低有效位都被设置，因为只有奇数被乘数会产生奇数倍； （2）如果将X设置为B的最高设置位，则Y不能大于sqrt（A）； （3）根据B中的当前位设置X或Y中的位。

下面的Python代码为我从Matt Timmermans的example code中挑选的随机对中的一个对进行了300次迭代。但是第一个进行了231,199次迭代：）

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,y | bit) + g(b - 1,x | bit,y)
    else:
      return g(b - 1,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 ""

输出：

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