博弈论

ICG博弈

所讨论的博弈问题满足以下条件：

•     玩家只有两个人，轮流做出决策。
•     游戏的状态集有限，保证游戏在有限步后结束，这样必然会产生不能操作者，其输。
•     对任何一种局面，胜负只决定于局面本身，而与轮到哪位选手无关。

经典的三种玩法

一、巴什博奕(Bash Game)

二、尼姆博奕(Nimm Game)

三、威佐夫博奕(Wythoff Game)

（一）巴什博弈

1堆n个石子每次最多取m个、至少取1个

Case 1:如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。

Case 2:n=(m+1)*r+s，(r为任意自然数，s≤m),那么先取者要拿走s个物品，如果后者拿走k(1≤k≤m)个，那么先取者再拿走m+1-k个，结果剩下(m+1)(r-1)个，以后保持这样的取法，那么先取者肯定获胜。

Case 3:n=r*(m+1)，先手拿走k(1≤k≤m)个，那么后手再拿走m+1-k个，结果剩下(m+1)(r-1)个，以后保持这样的取法，则后手胜，先手必败。

总之，要保持给对手留下（m+1）的倍数，就能最后获胜。

例题：两个人轮流报数，每次至少报一个，最多报十个，谁能报到100者胜。（等价于从一堆100个石子中取石子，最后取完的胜）

有一堆k个的石头，每人轮流拿1,2，..L个石头，数据范围是3 <= K <= 100 000 000 ，2 <= L < K。输入k的值，要求输出最小的L，使得后者胜。

首先想让后手胜，就必须把（1+L）的局面留给先手。这题没问我们谁会赢，问的是后手要赢的最小L值为多少。那我们就找到能被k整除的最小大于2的因数，之后减1输出就是答案了

红色的部分基于case3的公式，k代表n，r是倍数关系，m是要找的l。

k=r*(l+1)→r=k/(l+1)

r代表倍数关系，只要从小到大找到(n%(i+1)==0)

//#include<bits/stdc++.h>
#include<iostream>
using namespace std;
typedef long long ll;
const int N=100005;
ll n;//石子数量
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    ll i;
    for(i=2;i<n;i++)//依次找最小的因子
    {
        if(n%(i+1)==0)
        {
            cout<<i<<endl;
            break;
        }
    }
    if(i==n) cout<<0<<endl;//找不到的情况下输出0
    return 0;
}