For given two integers A and B, find a pair of numbers X and Y such that A = X*Y and B = X xor Y

Question

I'm struggling with this problem I've found in a competitive programming book, but without a solution how to do it.

For given two integers A and B (can fit in 64-bit integer type), where A is odd, find a pair of numbers X and Y such that A = X*Y and B = X xor Y. My approach was to list all divisors of A and try pairing numbers under sqrt(A) with numbers over sqrt(A) that multiply up to A and see if their xor is equal to B. But I don't know if that's efficient enough. What would be a good solution/algorithm to this problem?

Answer 1

You know that at least one factor is <= sqrt(A). Let's make that one X.

The length of X in bits will be about half the length of A.

The upper bits of X, therefore -- the ones higher in value than sqrt(A) -- are all 0, and the corresponding bits in B must have the same value as the corresponding bits in Y.

Knowing the upper bits of Y gives you a pretty small range for the corresponding factor X = A/Y. Calculate Xmin and Xmax corresponding to the largest and smallest possible values for Y, respectively. Remember that Xmax must also be <= sqrt(A).

Then just try all the possible Xs between Xmin and Xmax. There won't be too many, so it won't take very long.