请听第一道算法题：爱健身的小王

刚参加工作的小伙伴可能觉得算法没什么用处，会工程开发就行，会写业务就行。但是当你达到一定的水平以后，你会发现系统的瓶颈可能在于算法，一个好的算法和一个差的算法在系统性能上的表现有云泥之别。不止于此，学习和练习算法也能锻炼人的思维能力，不管你做什么事都会有潜移默化的影响。所以，总之一句话，让我们现在就开始学习算法吧！

今年实习生招聘差不多也接近尾声了，各大厂的笔试题目在网上都能找到。今天我们看一道美团的笔试题，比较容易。

题目如下图所示：

image.png

这种题目切忌一上来就暴力求解。首先要分析一下题目的规律。我们假设小王从正方形的左上角（记为原点）开始走起。

首先分析一下小王会在哪里停下来。小王从起点走n+1步后打了第一个标记，我们记为A点，再走n+1步又打一个标记，记为B点，以此类推。假设小王打了若干次标记后不是在A点停下来，比如是在B点停下来，那么往回退n+1步，小王上一次一定是在A点重复打了一个标记，这就有矛盾了，所以，小王一定是在A点停下来的。

这个结论一旦成立，说明小王在A点重复打标记之前的一次就是在原点打标记。我们记小王一共标记了m次，那么在原点打标记就是第m-1次打标记，而每打一次标记要走n+1步，所以到第m-1次打标记为止一共走了(n+1)(m-1)步，这(n+1)(m-1)步刚好等于周长的若干倍，即

(n+1)(m-1)=4n*k

从这个式子中可以看出，(n+1)(m-1)既是n+1的倍数，也是4n的倍数，又因为我们要找的m是让上式第一次成立的m，所以我们只要找出n+1和4n的最小公倍数，然后除以n+1即可得到答案。

所以m=[n+1, 4n] / (n+1) + 1

而最小公倍数[n+1, 4n] = (n+1)*4n / (n+1, 4n)

所以m = 4n / (n+1, 4n) + 1

到这里我们发现这道题的本质变成了求最大公约数问题(gcd)。最大公约数问题的代码网上到处都是。

最后附上golang版的代码：

package main

import (
  "fmt"
  "strconv"
  "bufio"
  "os"
  "strings"
)

func main() {
  var ts string
  var ns string
  fmt.Scanln(&ts)
  t, _ := strconv.Atoi(ts)
  
  inputReader := bufio.NewReader(os.Stdin)
  ns, _ = inputReader.ReadString('\n')
  ns = strings.Trim(ns, "\r\n")
  n_slice := strings.Split(ns, " ")
  for i := 0; i < t; i++ {
    n, _ := strconv.Atoi(n_slice[i])
    fmt.Println(4*n/gcd(n+1, 4*n)+1)
  }
}

func gcd(a, b int) int {
  if b == 0 {
    return a
  } else {
    return gcd(b, a%b)
  }
}

大家想看更详细的视频解答的话，可以上b站或者斗鱼等网站上搜“大雪菜”（这个up主是北大的大神级人物），能找到相关的视频。

欢迎关注博主个人微信公众号~~~

image