逆乘法

Question

我有以下号码；让我们称它为第一

-1757151608

那我还有第二个号码，就叫它未知吧

94507795

最后，我有了产品，我们称它为二号产品

-1000

如果我将表格中的前两个数字相乘，我得到的答案是 -1000。问题是，我手头有第一和第二，但我需要从中得到未知数。

我已经尝试使用 BigInteger class 和它的一些功能，但没有成功。

提前致谢。

Answer 1

这个乘法是不可能逆的。

首先，我们取第一个数的补码。

3904635256 = 2147483648 - -1757151608

接下来，我们将乘以第二个数字

369018468323820520 = 3904635256 * 94507795

现在，这是棘手的部分。我们将乘积转换为十六进制，并删除大于 32 位整数的数字。

51F0457800003E8 (hex) = 369018468323820520 (decimal)
800003E8 = 51F0457800003E8 moved to a 32 bit signed integer

现在，我们将十六进制值转换回十进制

2147484648 (dec) = 800003E8 (hex)

最后，我们取小数的补码

-1000 = 2147483648 - 2147484648

由于我们丢弃了 51F0457 (hex)，因此我们无法将其取回。这个操作的逆操作是不可能的。

Answer 2

我相信你想要的是将 -1000 乘以 -1757151608 modulo 2^32 的乘法逆元；参见，例如 the calculation in Wolfram Alpha。

我写了一个程序，我相信它可以正确地计算出你问题的答案，如果存在的话。

public class InverseMultiplication {

  // multiplicative inverse of a multiplied by b mod 2^32
  public static long invertAndMultiply(long a, long b) { 
    // take out common factors of 2
    while (a % 2 == 0 && b % 2 == 0) {
      a /= 2;
      b /= 2;
    }
    long m = 256L*256L*256L*256L; // modulus is 2^32
    long r = m;
    long nr = a;
    long t = 0;
    long nt = 1;
    while (nr != 0) {
      long q = r/nr;
      long tmp;
      tmp = nt; nt = t - q*nt; t = tmp;
      tmp = nr; nr = r - q*nr; r = tmp;
    }
    if (r > 1) throw new IllegalArgumentException(a + " has no inverse");
    t = (t*b) % m;
    while (t < Integer.MIN_VALUE) t += m;
    while (t > Integer.MAX_VALUE) t -= m;
    return t;
  }

  public static void main(String[] args) {
    long twoPow32 = 256L*256L*256L*256L;
    int n1 = -1757151608;
    int n2 = -1000;
    long unk = invertAndMultiply(n1,n2);
    System.out.println(unk);
    long pro = n1 * unk % twoPow32;
    if (pro > Integer.MAX_VALUE) pro -= twoPow32;
    System.out.println(pro);
    int pro1 = -1757151608 * 94507795;
    System.out.println(pro1);
  }
}

但是，有几点需要注意。如果您的 "number one" 是奇数，程序会很快找到一个唯一的答案。

偶数 "number one" 不会有逆数 mod 2^32，所以通常情况下你会倒霉。但是，如果您的 "number two" 也是偶数，您可以继续将两者除以 2 ("taking out common factors of 2")，直到一个或两个都为奇数。希望 "number one" 是奇数，在这种情况下你会得到答案；如果 "number one" 即使在取出 2 的所有公因数之后，您也不会得到任何答案。那样的话就没有答案了。

如果偶数有一个答案，那就不止一个答案。如果您运行我的程序，您会发现它得出的答案与您的不同。

请检查一下，让我知道它是否按您期望的方式工作。

逆乘法

Reverse Multiplication

java

math

biginteger

modulus