P8901 的题解

· · 题解

前言

这次 USACO 考的非常不错，拿到了 0 分的高分。

死磕 T1 三小时最后发现没开 long long 。

T2 博弈论完全看不懂。

T3 压根没看。

赛后才发现 T2 的推明白公式代码难度一点没有。

不说了，上题解。

思路

相关

此题是巴什博弈的变种。（不过没了解也没关系，本身内容也不难，可以不学）

规律

之后我们再来看这道题，简单的来讲就是解决这么一个问题。

两个人拿石子，每次只能拿质数个或者一个，谁拿到最后一个谁就赢了，问谁有必胜策略，最少需要几步。

经过利用人脑计算完小数据后，我们得出来一个规律，任何是四的倍数的石子数总会是后手先赢，否则是先手赢。

证明

证明输赢

接下来我们就要想怎么来证明我们找出的规律了。

如果我们想让后手赢，那么石子的数量一定是 4k 的形式。

还有一点我们可以确定，如果石子数为 4 ，后手一定赢。（手动推出来的）

对于先手，只能拿质数个或者一个，而拿的数量一定不可能是 4k 的形式。

那么，先手拿完了之后，石子的数量也只可能为 4k+1,4k+2,4k+3 这三种形式。

如果剩下的数是质数，后手直接拿完，否则把石子的数量变为 4k 的形式。（拿一个，拿两个或者拿三个）

持续这样的过程直到只剩下 4 。

由于 4 我们可以通过手动证明，所以后手必赢。

那么如何证明 4k+1,4k+2,4k+3 的形式下先手必赢呢，同理。

先手可以先把石子的数量变为 4k 的形式，这样自己就可以变为后手，然后拥有必胜策略。（拿一个，拿两个或者拿三个）

证明步数

对于后手必胜的情况，先手一定想让步数下的越多越好，那么先手就会选择每次只拿2个，由于后手想让棋子的数量变为 4k 的形式，所以后手必须拿4k+2个，而只有 k=0 的情况下 4k+2 是质数，所以后手每次也只能拿两个。

那么很快我们就可以得出证明，当石子是 4k 的形式下，在 x/4+1 轮时后手赢。（ x 为石子数量，一轮是指先手后手都拿一次）

而先手必赢的情况，就稍微有点复杂了，先手想先减去一个质数，使得石子数量变成 4k 的形式，之后按照后手必赢的情况去做。

当然，如果希望步数越少越好，我们一定也希望那个质数越大越好，所以得出来的公式是当石子不在 4k 的形式下，在 (x-p)/4+1 轮时先手赢。

过程

说完基本原理之后，我们来说具体代码实现。

我们先打一个表，代表着当石头数为多少时谁获胜，并且用了多少轮。

对于 4k 这种格式，直接套公式。

而对于 4k+1,4k+2,4k+3 这种格式，我们可以通过欧拉筛分别找出格式为 4k+1,4k+2,4k+3 最大的质数，这样石子数量减完了之后就会变成 4k 的形式，让后套公式。

解决完核心问题了之后，外围的问题我就不多讲了。

AC CODE

#include <iostream>
using namespace std;
const int N=5e6+5;
bool isprime[N];
int prime[N];
int n,cnt;
int s[4];//统计格式为4k+1,4k+2,4k+3的最大质数
int ans[N];
int t;
void euler()//欧拉筛
{
    int i,j;
    isprime[1]=true;
    ans[1]=1;
    s[1]=1;
    for(i=2; i<=N; i++)
    {
        if(!isprime[i])
        {
            prime[++cnt]=i;
            if(i%4!=0)
                s[i%4]=i;//更新最大质数数组
        }
        for(j=1; j<=cnt && i*prime[j]<=N; j++)
        {
            isprime[i*prime[j]]=true;
            if(i%prime[j]==0)
                break;
        }
        if(i%4==0)
            ans[i]=i/4+1;//套公式
        else
            ans[i]=(i-s[i%4])/4+1;//套公式
    }
}
int main()
{
    int i;
    euler();
    cin>>t;
    while(t--)
    {
        cin>>n;
        int minx1=1e9,mark1;
        int minx2=1e9,mark2;
        for(i=1; i<=n; i++)//不多解释了，作者的代码很烂，不一定要学习我的，自己写也行
        {
            int temp;
            cin>>temp;
            if(temp%4==0)
            {
                if(minx2>ans[temp])
                {
                    minx2=ans[temp];
                    mark2=i;
                }
            }
            else
            {
                if(minx1>ans[temp])
                {
                    minx1=ans[temp];
                    mark1=i;
                }
            }
        }
        if(minx1<minx2)
            cout<<"Farmer John"<<endl;
        else if(minx1>minx2)
            cout<<"Farmer Nhoj"<<endl;
        else
        {
            if(mark1<mark2)
                cout<<"Farmer John"<<endl;
            else
                cout<<"Farmer Nhoj"<<endl;
        }
    }
    return 0;
}