题目大意

$Euclid$和$Pythagoras$在玩取石子游戏，一开始有n颗石子

$Euclid$为先手，他们按如下规则轮流操作：

1. 若为$Euclid$操作，如果$n< p$，则他只能新放入$p$颗石子，否则他可以拿走$p$的倍数颗石子

2. 若为$Pythagoras$操作，如果$n< q$，则他只能新放入$q$颗石子，否则他可以拿走$q$的倍数颗石子

拿光所有石子者胜利，假设他们都以最优策略操作，那么获胜者是谁，或者没有胜利者？

数据范围

$1\leqslant t\leqslant 1000$，表示共玩$t$局游戏，$1\leqslant p,q,n\leqslant 10^9$

题解

这是一道博弈论，膜拜大神系列

程序

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

int n,p,q,t,g;
inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
inline int cal(int p,int q,int n){return (n%p<q)&&(n%p%(p-q)==0);}

int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&p,&q,&n);
        g=gcd(p,q);
        if (n%g){puts("R");continue;}
        p/=g;q/=g;n/=g;
        if (p==q) puts("E");
        else if (p>q){
            if (n<p) puts("P");
            else puts(cal(p,q,n)?"E":"P");
        }
        else{
            if (n<p){
                if (n+p<q) puts("E");
                else puts(cal(q,p,n+p)?"P":"E");
            }
            else puts("E");
        }
    }
}