結果

問題 No.7 プライムナンバーゲーム
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-02-21 16:10:43
言語 Go
(1.22.1)
結果
AC  
実行時間 135 ms / 5,000 ms
コード長 3,067 bytes
コンパイル時間 13,694 ms
コンパイル使用メモリ 209,704 KB
実行使用メモリ 98,812 KB
最終ジャッジ日時 2023-09-29 08:26:04
合計ジャッジ時間 15,590 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 135 ms
98,756 KB
testcase_03 AC 13 ms
10,500 KB
testcase_04 AC 4 ms
5,728 KB
testcase_05 AC 5 ms
5,732 KB
testcase_06 AC 43 ms
33,788 KB
testcase_07 AC 29 ms
23,296 KB
testcase_08 AC 15 ms
12,612 KB
testcase_09 AC 62 ms
44,304 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 30 ms
23,252 KB
testcase_12 AC 103 ms
75,704 KB
testcase_13 AC 106 ms
79,876 KB
testcase_14 AC 133 ms
94,540 KB
testcase_15 AC 129 ms
98,812 KB
testcase_16 AC 120 ms
92,460 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
)

var E *eratosthenesSieve
var P []int

func init() {
	E = newEratosthenesSieve(1e4 + 10)
	P = E.GetPrimes()
}

func main() {
	// 给定一个数n(2<=n	<=1e5)
	// 两个人交互变化数字,可以将每个数减去一个素数
	// 不能继续操作就算输,问先手是否必胜
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n int
	fmt.Fscan(in, &n)

	dag := make([][]int, n+10) // 状态i定义为当前数字为i
	for num := 2; num <= n; num++ {
		for _, p := range P {
			if num-p < 2 {
				break
			}
			dag[num] = append(dag[num], num-p)
		}
	}

	grundy := GrundyNumber(dag)
	if grundy[n] == 0 {
		fmt.Println("Lose")
	} else {
		fmt.Println("Win")
	}
}

// dag: 博弈的每个状态组成的有向无环图.
//  返回值: 每个状态的Grundy数.
//  grundy[i] = mex{grundy[j] | j in dag[i]}.
//  - 如果grundy为0,则先手必败,否则先手必胜.
//  - 若一个母状态可以拆分成多个相互独立的子状态，`则母状态的 SG 数等于各个子状态的 SG 数的异或。`
func GrundyNumber(dag [][]int) (grundy []int) {
	order, ok := topoSort(dag)
	if !ok {
		return
	}

	grundy = make([]int, len(dag))
	memo := make([]int, len(dag)+1)
	for j := len(order) - 1; j >= 0; j-- {
		i := order[j]
		if len(dag[i]) == 0 {
			continue
		}
		for _, v := range dag[i] {
			memo[grundy[v]]++
		}
		for memo[grundy[i]] > 0 {
			grundy[i]++
		}
		for _, v := range dag[i] {
			memo[grundy[v]]--
		}
	}

	return
}

func topoSort(dag [][]int) (order []int, ok bool) {
	n := len(dag)
	visited, temp := make([]bool, n), make([]bool, n)
	var dfs func(int) bool
	dfs = func(i int) bool {
		if temp[i] {
			return false
		}
		if !visited[i] {
			temp[i] = true
			for _, v := range dag[i] {
				if !dfs(v) {
					return false
				}
			}
			visited[i] = true
			order = append(order, i)
			temp[i] = false
		}
		return true
	}

	for i := 0; i < n; i++ {
		if !visited[i] {
			if !dfs(i) {
				return nil, false
			}
		}
	}

	for i, j := 0, len(order)-1; i < j; i, j = i+1, j-1 {
		order[i], order[j] = order[j], order[i]
	}
	return order, true
}

//
//
//
//
// 埃氏筛
type eratosthenesSieve struct {
	minPrime []int
}

func newEratosthenesSieve(maxN int) *eratosthenesSieve {
	minPrime := make([]int, maxN+1)
	for i := range minPrime {
		minPrime[i] = i
	}
	upper := int(math.Sqrt(float64(maxN))) + 1
	for i := 2; i < upper; i++ {
		if minPrime[i] < i {
			continue
		}
		for j := i * i; j <= maxN; j += i {
			if minPrime[j] == j {
				minPrime[j] = i
			}
		}
	}
	return &eratosthenesSieve{minPrime}
}

func (es *eratosthenesSieve) IsPrime(n int) bool {
	if n < 2 {
		return false
	}
	return es.minPrime[n] == n
}

func (es *eratosthenesSieve) GetPrimeFactors(n int) map[int]int {
	res := make(map[int]int)
	for n > 1 {
		m := es.minPrime[n]
		res[m]++
		n /= m
	}
	return res
}

func (es *eratosthenesSieve) GetPrimes() []int {
	res := []int{}
	for i, x := range es.minPrime {
		if i >= 2 && i == x {
			res = append(res, x)
		}
	}
	return res
}
0