1
2
3
4
5
6
unsigned short i,j;
int count = 0;
for (i= 0, j=2; i!=j; i+=5, j+=7) {
    count++;
}
// 此时count是多少？

1、通用解法

  很显然，当i和j相遇的时候，他们俩必然在同一个位置。好吧，这是一句大废话。不过这句废话怎么表示呢?

1
2
3
4
5
//i的步长是5， j的步长是7。假设他们x步后相遇，所以他们走过的总路径分别是
long iSum = 5 * x;
long jSum = 7 * x + 2; //起始位置算在总路径中
// 那么他们现在的位置相等
iSum % 65536 == jSum % 65536; //此表达式为真

  好了，经过上面的分析，通用解法已经出来了。

1
2
3
4
5
6
7
int count = 0;
while (1) {
   if ((7 * count + 2) % 65536 == (5 * count) % 65536) {
        break;
   }
   count++;
}

  这个循环，跑去吧。

2、改进解法

  通用解法优点是很简单，很容易理解。但是，一旦模的值变大，循环次数太多，更本不是人能算出来的，不信？你自己算算上面那个答案。

  该怎么简化呢？注意下这个等式:

1
iSum % 65536 == jSum % 65536;

  取余操作是很麻烦的，而且我们穷举的数值是sum值，一步步在累加，这样实在太麻烦了。

1
2
iSum % 65536 == jSum % 65536    ==>
iSum - jSum == 65536 * n  //n是某个合适的值

  上面的推导过程不详细说明了，很简单。

1
2
7 * count + 2 - 5 * count == 65536 * n;
count = (65536 * n - 2) / 2

  好了，直接求count的算法就出来了。有一点需要注意，count 是一个整数。所以需要加一步判断。

1
2
3
4
5
6
7
8
9
10
int count = 0;
int n = 1;
while (n > 0) {
    int temp = 65536 * n - 2;
    if (!(tmep % 2)) {
       count = temp / 2;
       break;
    }
    n++;
}

  好了，这个算法循环的次数明显要比上一个小好多好多，并且我们自己也可以算出答案。对这个题来说，n = 1的时候就是合适的值，只用循环一次就好。

  可以看出，上面的改进解法可以作为一般的解题思路。我们可以写这么一段代码作为通用代码，使用的时候只需要替换几个参数就可以了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int getCount(int mod, int aheadStep, int vDiff) {
    int count = -1;
    int n = 1;
    // 速度差不小于1
    if (vDiff < 1) {
       return -1;
    }
    // 如果没找到，n溢出后变成负数退出
    while (n > 0) {
       int temp = mod * n - aheadStep;
       if (!(tmep % vDiff)) {
          count = temp / vDiff;
          break;
       }
       n++;
    }
    return count;
}