【jzoj4909】【李电下棋】【数论】【结论】

题目大意

有1到n个格子，一开始在a，b处有棋子，k能放棋子当且仅当i，j有棋子，k=i+j或k=|i-j|，不能放的人输，问先手必胜还是必输。

解题思路

发现k是gcd（a，b）的倍数时一定可达，算出有多少个格子，判断奇偶性即可。

code

#include<cmath> #include<cstdio> #include<algorithm> #define LL long long #define min(a,b) ((a<b)?a:b) #define max(a,b) ((a>b)?a:b) #define fo(i,j,k) for(int i=j;i<=k;i++) #define fd(i,j,k) for(int i=j;i>=k;i--) using namespace std; int const maxn=1e6,maxa=1e6; int t;LL n,a,b; LL gcd(LL a,LL b){ LL c; while(a%b){ c=a%b; a=b; b=c; } return b; } int main(){ //freopen("chess.in","r",stdin); //freopen("chess.out","w",stdout); freopen("d.in","r",stdin); freopen("d.out","w",stdout); scanf("%d",&t); fo(i,1,t){ scanf("%lld%lld%lld",&n,&a,&b); LL gc=gcd(a,b); if(n/gc%2)printf("lidian\n"); else printf("wfl\n"); } return 0; }