[algorithm] 두 개의 정수 A와 B에 대해 A = X * Y와 B = X xor Y가되도록 숫자 X와 Y의 쌍을 찾으십시오.

Program / 글쓴이

경쟁 프로그래밍 책에서 찾은이 문제로 어려움을 겪고 있지만 해결 방법이 없습니다. A 가 홀수 인

두 개의 정수 A 와 B (64 비트 정수 유형에 적합)에 대해 A = X * Y와 B = X xor Y와 같은 숫자 X와 Y의 쌍을 찾으십시오 . A의 모든 제수와 sqrt (A) 아래의 숫자를 sqrt (A) 이상의 숫자와 짝을 이루어 A 까지 곱하고 xor가 B와 같은지 확인하십시오 . 그러나 그것이 충분히 효율적인지 모르겠습니다. 이 문제에 대한 좋은 해결책 / 알고리즘은 무엇입니까?

답변

우리가 알고있는 규칙을 관찰하는 간단한 재귀는 다음과 같습니다. (2) X를 B의 가장 높은 설정 비트로 설정하면 Y는 sqrt (A)보다 클 수 없습니다. (3) B의 현재 비트에 따라 X 또는 Y의 비트를 설정한다.

다음 Python 코드는 Matt Timmermans의 예제 코드 에서 선택한 임의의 쌍 중 하나를 제외하고 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, 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 ""

산출:

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

답변

적어도 하나의 요소가 <= sqrt (A)라는 것을 알고 있습니다. X를 하나 만들어 봅시다.

X 단위의 비트 길이는 A 길이의 약 절반입니다.

따라서 sqrt (A)보다 값이 높은 X의 상위 비트는 모두 0이며 B의 해당 비트는 Y의 해당 비트와 동일한 값을 가져야합니다.

Y의 상위 비트를 알면 해당 인수 X = A / Y에 대해 아주 작은 범위가 제공됩니다. Y의 최대 값과 최소값에 각각 해당하는 Xmin과 Xmax를 계산합니다. Xmax도 <= sqrt (A) 여야합니다.

그런 다음 Xmin과 Xmax 사이에 가능한 모든 X를 시도하십시오. 너무 많지 않으므로 시간이 오래 걸리지 않습니다.

답변

이 문제를 해결하는 또 다른 간단한 방법은 낮은한다는 사실에 의존 n 개의 XY와 X XOR Y의 비트 만 낮은에 따라 N 당신이 낮은에 대한 가능한 답변을 사용할 수 있습니다, 따라서 X와 Y의 비트 N 제한하는 비트 완료 될 때까지 하위 n + 1 비트에 대한 가능한 답변 .

불행히도 하나의 n에 대해 둘 이상의 가능성이있을 수 있다는 것을 알아 냈습니다 . 나는 얼마나 많은 가능성이 있을지 모르지만, 아마도 너무 자주는 아닐 것이므로 경쟁 상황에서는 괜찮을 것입니다. 확률 적으로 n 비트에 대한 솔루션은 n + 1 비트에 대해 0 또는 2 개의 솔루션을 동일한 확률로 제공 하기 때문에 몇 가지 가능성 만 있습니다 .

무작위 입력에 대해서는 꽤 잘 작동하는 것 같습니다. 테스트에 사용한 코드는 다음과 같습니다.

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 에서 결과를 확인할 수 있습니다.

보통 수만 번의 검사 만 필요한 것 같습니다.

답변