牛客小白月赛13 I题(博弈论)
题目:[链接]
题目描述:
小A也听说了取石子这个游戏,也决定和小B一起来玩这个游戏。总共有n堆石子,双方轮流取石子,每次都可以从任意一堆中取走任意数量的石子,但是不可以不取。规定谁先取完所有的石子就获胜。但是小A实在是太想赢了,所以在游戏开始之前,小A有一次机会,可以趁小B不注意的时候选择其中一堆石子拿走其中的k个,当然小A也可以选择不拿石子。小A先手。双方都会选择最优的策略,请问在这样的情况下小A有没有必胜的策略,如果有输出YES,否则就输出NO。
费马小定理:a是不能被质数p整除的正整数,则有a^(p-1)≡ 1 (mod p)
推导:a^(p−1) ≡ 1 (mod p) = a*a^(p−2 )≡ 1 (mod p) ;
则a的逆元 为 a^(p−2)。利用费马小定理求逆元的前提强调p一定是质数。
说这些你可能不太明白,先看一道题就明白了,