java - 一个编号变量生成另一个编号变量

Question

所以你从四个变量开始。

Variable A = Any #;
Variable B = Any #;
Variable C = 1;
Variable D = 1;

变量 C 和 D 始终等于 1。

问题:

当变量 C 可能将其自身添加到 D 计数并且变量 D 可能将其自身添加到 C 计数时，C 和 D 需要多少次添加才能与变量 A 和 D 相关。

例如

Variable A = 4;
Variable B = 7;

Output -> 4

这是因为模式 (C=1, D=1):

C+=D        C+=D        D+=C        D+=C         / Equations    
C=2 D=1 (1) C=3 D=1 (2) C=3 D=4 (3) C=3 D=7 (4) / Output (4 in total)

如何获得进一步的结果？

好吧，我想出了一个方法，你可以向后推算出需要添加的总数量。

count = 0;

if(A == B)
{
   "return impossible";
}
else if (A > B)
{
    A = A - B;
    count++;
}
else if (B > A)
{
    B = B - A;
    count++;
}

<强>???令人费解的问题？？？

这对于较小的数字非常有效，但问题是程序必须能够处理高达 10^50 次方的数字。我的所有变量都存储在 BigInteger 变量中，并且我已经完成了 4/5 的测试用例。最后一个测试用例由于运行时错误而失败。测试用例未知，但我有预感它是 10^50。我的问题是是否有任何方法可以优化解决方案以更快地接收加法次数，或者也许有另一种方法可以用方程解决问题？提前致谢!

为了进一步调试上述伪代码(我的代码):

    public static void main (String[] args) {
    System.out.println(answer("5000000000000000000000000000000000000000", "5")); //vA big number and a small number
}

public static String answer(String M, String F) 
{
    String str = testPossibilities(M, F);

    return str;
}

public static String testPossibilities(String M, String F)
{
      BigInteger nM = new BigInteger(M);
      BigInteger nF = new BigInteger(F);
      BigInteger inc = new BigInteger("1");
      BigInteger count = new BigInteger("0");

      while (BigInteger.valueOf(1).compareTo(nM) == -1 || BigInteger.valueOf(1).compareTo(nF) == -1) 
      {
          BigInteger offset = new BigInteger("" + (nM.divide(new BigInteger("2"))));

          System.out.print(nM + " " + nF + "\n"); // Print results

          if(nM.compareTo(nF) == 0 || BigInteger.valueOf(1).compareTo(nM) == 1 || BigInteger.valueOf(1).compareTo(nF) == 1) // If equal then not possible
          {
              return "impossible";
          }
          else if(nM.compareTo(nF) == 1)
          {
              if(nM.compareTo(nF.multiply(offset)) == 1)
              {
                  nM = nM.subtract(nF.multiply(offset));
                  count = count.add(nF.multiply(offset));                 
              }
              else
              {
                  nM = nM.subtract(nF);
                  count = count.add(inc);                     
              }
          }
          else if(nF.compareTo(nM) == 1)
          {
               nF = nF.subtract(nM);
               count = count.add(inc);
          }

      }

      if (BigInteger.valueOf(1).compareTo(nM) == 0 && BigInteger.valueOf(1).compareTo(nF) == 0) //If everything went ok then return the number
      {
          return "" + count;
      }

      return "impossible";

}

Answer 1

我研究了一种更快的算法，计算(5000000000000000000000000000000000000000,5)需要将近一秒钟，并且它基于mod:

1. 在 ( A != B ) && ( A != 0 ) && ( B != 0 ) 期间保持计算。
2. 计数 = 除以最大值/最小值(nF 与 nM )。如果大于 0，则返回该值，否则返回 1。
3. nM = nM mod nF。
4. nF = nF mod nM。

然后，迭代之后我们可以分析结果:

1. 如果nF或nM达到0，但另一个数字!= 1，这是不可能的。
2. 否则将成功计数返回给 M 和 F。

方法:

public static String answer( String M, String F )
{
     BigInteger nM = new BigInteger(M);
     BigInteger nF = new BigInteger(F);
     long count = 0;


     while ( !nM.equals ( nF ) && !nM.equals ( new BigInteger ( "0" ) ) && !nF.equals ( new BigInteger ( "0" ) ) ) 
     {
         BigInteger divide = (nF.max ( nM )).divide ( nF.min ( nM ) );
         count += divide.compareTo ( new BigInteger ( "0" ) ) == 1 ? divide.longValue ( ) : 1;
         BigInteger originalNM = nM;
         BigInteger originalNF = nF;
         nM = originalNM.mod ( originalNF );
         nF = originalNF.mod ( originalNM );
         System.out.println(nM + " " + nF + " " + count); // Print results
     }
     if (nM.intValue ( ) == 0 && nF.intValue ( ) != 1) return "impossible " + (count-1);
     if (nM.intValue ( ) != 1  && nF.intValue ( ) == 0) return "impossible " + (count-1); 

     return "" + (count-1);

}

I/O 示例:

Input: 
( "5000000000000000000000000000000000000000" , "5" )

Output: 
0 5 6873995514006732800
impossible 6873995514006732799

Input:
( "123123123" , "43" )

Output:
19 43 2863328
19 5 2863330
4 5 2863333
4 1 2863334
0 1 2863338
2863337

Input:
( "4" , "7" )

Output:
4 3 1
1 3 2
1 0 5
4

注意:此算法一直到 0，因此正确的count 将为count-1。