2021-12-03：石子游戏 IV。Alice 和 Bob 两个人轮流玩一个

package main

import (
    "fmt"
    "math"
)

func main() {
    for i := 1; i <= 100; i++ {
        ret := winnerSquareGame3(i)
        ret2 := numSquares(i)
        fmt.Println(i, ret, ret2)
    }
}

func winnerSquareGame3(n int) bool {
    dp := make([]bool, n+1)
    for i := 1; i <= n; i++ {
        for j := 1; j*j <= i; j++ {
            if !dp[i-j*j] {
                dp[i] = true
                break
            }
        }
    }
    return dp[n]
}

// 判断是否为完全平方数
func isPerfectSquare(x int) bool {
    y := int(math.Sqrt(float64(x)))
    return y*y == x
}

// 判断是否能表示为 4^k*(8m+7)
func checkAnswer4(x int) bool {
    for x%4 == 0 {
        x /= 4
    }
    return x%8 == 7
}

func numSquares(n int) int {
    if isPerfectSquare(n) {
        return 1
    }
    if checkAnswer4(n) {
        return 4
    }
    for i := 1; i*i <= n; i++ {
        j := n - i*i
        if isPerfectSquare(j) {
            return 2
        }
    }
    return 3
}