【JZOJ4909】李电下棋

Description

Solution

这题我们可以找规律，是gcd(a,b)倍数的格子都可以被下到。

证明： gcd(a,b)=gcd(a,a−b)=gcd(a,a+b)

Code

#include<cstdio> #include<cstdlib> #include<algorithm> #define fo(i,j,k) for(int i=j;i<=k;i++) #define fd(i,j,k) for(int i=j;i>=k;i--) #define ll long long using namespace std; ll gcd(ll x,ll y) { ll z; while(x%y!=0) { z=x%y; x=y; y=z; } return y; } int main() { freopen("chess.in","r",stdin); freopen("chess.out","w",stdout); int T; scanf("%d",&T); while(T--) { ll n,a,b; scanf("%lld %lld %lld",&n,&a,&b); if(n/gcd(a,b)%2==1) printf("lidian"); else printf("wfl"); printf("\n"); } }