如何建立日心说算法？

Question

鉴于此问题：

考虑轨道系统中的两个行星：地球和火星。假设地球正好在365个地球日内绕太阳运行，而火星正好在687个地球日绕太阳公转。因此，地球的轨道在第0天开始并持续到第364天，然后在第0天开始。火星的轨道运行类似，但是在687天的时间尺度上。

我们想知道在这两个行星都在一天之前需要多长时间。它们的轨道同时为0。编写一个可以确定这个的程序。

输入格式：

第一行输入包含一个整数N，表示测试用例的数量。 N行跟随。每个测试用例包含两个整数E和M.这些表示地球和火星在各自轨道上的几天。

输出格式：

对于每种情况，显示案例编号，然后显示最小天数，直到两个行星都在其轨道的第0天。遵循示例输出的格式。

样本输入1

0 0

364 686

360 682

0 1

1 0

样本输出1

案例1：0

案例2：1

案例3：5

案例4：239075

案例5：11679

我尝试使用模块解决问题，但似乎不正确

static string readInput;
static string firstStr = "";
static string secondStr = "";
static int firstInput;
static int secondInput;
static int testCases = 10;
static int caseNumber = 1;
static int outPut;
caseNumber <= testCases

static void Main(string[] args) {
  //recall runProcess as long caseNumber is less or equal testCases
  while (caseNumber <= testCases) {
    runProcess();
    Console.WriteLine("Case " + caseNumber + ": " + outPut);
    caseNumber++;
  }
}

从控制台读取输入：

/// <summary>
/// This is the main process, is extracted to void so we can recall it.
/// </summary>
public static void runProcess() {
  readInput = Console.ReadLine();
  if (readInput != null) {
    for (int i = 0; i < readInput.Length; i++) {
      secondStr = secondStr + readInput[i];
      if (readInput[i] == ' ') {
        firstStr = secondStr;
        secondStr = "";
        continue;
      }
    }
  }
  firstInput = Convert.ToInt32(firstStr);
  secondInput = Convert.ToInt32(secondStr);
  outPut = atZero(firstInput, secondInput);
}

/// <summary>
/// This method takes the input data from the console to later determine the zero point
/// </summary>
/// <param name="earthDays"></param>
/// <param name="marsDays"></param>
/// <returns></returns>
public static int atZero(int earthDays, int marsDays) {
  int earthOrbit = 365;
  int marsOrbit = 687;
  int modEarth = earthOrbit;
  int modMars = marsOrbit;
  int earthDistinction = earthOrbit - earthDays;
  int marsDistinction = marsOrbit - marsDays;
  if ((modInverse(earthDistinction, marsDistinction, modMars)) == 0) {
    return (modInverse(marsDistinction, earthDistinction, modEarth)) * marsDistinction;
  } else {
    return (modInverse(earthDistinction, marsDistinction, modMars)) * earthDistinction;
  }
}

mod反转

/// <summary>
/// The method below takes a denominator, numerator and a mod to later invert the mod.
/// </summary>
/// <param name="denominator"></param>
/// <param name="numerator"></param>
/// <param name="mod"></param>
/// <returns>modInverse</returns>
static int modInverse(int denominator, int numerator, int mod) {
  int i = mod, outputAll = 0, d = numerator;
  while (denominator > 0) {
    int divided = i / denominator, x = denominator;
    denominator = i % x;
    i = x;
    x = d;
    d = outputAll - divided * x;
    outputAll = x;
  }
  outputAll %= mod;
  if (outputAll < 0) outputAll = (outputAll + mod) % mod;
  return outputAll;
}

有没有办法解决没有模块的问题？

谢谢。

Answer 1

计算解决方案的直接方法可能是这种方法：

private static int DaysTillBothAt0(int currentEarthDay, int currentMarsDay)
{
    int result = 0, earth = currentEarthDay, mars = currentMarsDay;
    while (earth != 0 || mars != 0)
    {
        result += 1;
        earth = (earth + 1) % 365;
        mars = (mars + 1) % 687;
    }

    return result;
}

这当然不是最快的算法或数学上非凡的优雅，但对于所需的数据范围，性能在这里根本不重要。 （不过我不知道老师的期望）。

它只是计算轨道前进，直到它们在0相遇。

您可以将此用于此类测试用例：

result = DaysTillBothAt0(0, 0); // 0
result = DaysTillBothAt0(364, 686); // 1
result = DaysTillBothAt0(360, 682); // 5
result = DaysTillBothAt0(0, 1); // 239075
result = DaysTillBothAt0(1, 0); // 11679