【算法】博弈论+数论

【题意】给定n个石子，两人轮流操作，规则如下：

轮到先手操作时：若石子数<p添加p个石子，否则拿走p的倍数个石子。记为属性p。

轮到后手操作时：若石子数<q添加q个石子，否则拿走q的倍数个石子。记为属性q。

拿走所有石子的人胜利，问先手是否必胜，或输出游戏会永远进行下去。

【题解】学习自： by popoqqq

首先博弈过程可以表示为不定方程ap+bq=n。

然后由扩欧可知此方程有解当且仅当gcd(a,b)|n，无解则永远进行下去。

方程有解时，两边同除gcd简化运算，p/=d,q/=d,n/=d，此时p,q互质，由于方程有解，一定能拿完，那么考虑谁先拿完。

 

对于一个状态(p,q,n)表示先手操作属性p，后手操作属性q，当前剩余n石子，p>q，有以下两种重要情况：

★1.n<p，先手必败。

证明：(p,q,n)--->(q,p,n+p)--->(p,q,(n+p)%q)，由于(n+p)%q<q，所以先手方p只能被迫一直增加，最终一定由q方拿完。

★2.n>p，当且仅当(p-q)|(n%p)&&(n%p<q)时先手必胜。

证明：若n%p>=q，那么就回到了第一种情况的第二步，先手必败。

若n%p<q，则先手必须取模到比q小避免必败，然后后手就被迫+q，先手再-p，后手再+q。

如此每次循环石子堆都会减少(p-q)，如果减少到0则先手胜，如果直接减到负数其实就是不够-p的情况，则又回到情况1的第二步，先手必败。

所以当且仅当(p-q)|(n%p)&&(n%p<q)时先手必胜。

 

讨论完重要情况后，开始对问题本身分情况讨论：

1.p=q=1时，先手必胜。

2.p>q,p>n，回归重要情况1，先手必败。

3.p>q,p<=n，回归重要情况2，当且仅当(p-q)|(n%p)&&(n%p<q)时先手必胜。

4.p<q,p>n，先手被迫+p，若n+p<q，后手回归重要情况1，先手必胜。若n+p>=q，后手回归重要情况2，当且仅当(q-p)|((n+p)%q)&&((n+p)%q<p)时先手必败。

5.p<q,p<=n，先手变成n%p，后手回归重要情况1，先手必胜。

#include
      
       #include
       
        #include
        
         using namespace std;int gcd(int a,int b){
    return !b?a:gcd(b,a%b);}bool calc(int p,int q,int n){
    return n%p
         
          q&&p>n)printf("P\n");else        if(p>q&&p<=n){
    if(calc(p,q,n))printf("E\n");else printf("P\n");}else        if(p
          
           n){
    if(n+p