思路:求1000以内的每个数的sg值,最后异或为0则先手必败,否则先手输
因为m,n,p都小于1000,所以只要求前15个斐波那契数就可以了 ,打表解决;
#include <iostream> #include <fstream> #include <cmath> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; int fb[]={1,2,3,5,8,13,21,34,55,89,144,233,377,610,987}; int sg[1001]; bool b[1001]; int m,n,p; void getsg() { memset(sg,0,sizeof(sg)); for(int i=1;i<=1000;i++) { memset(b,true,sizeof(b)); for(int j=0;j<15;j++) { if(i<fb[j]) break; b[sg[i-fb[j]]]=false; } for(int j=0;j<=1000;j++) if(b[j]) { sg[i]=j;break; } } } int main() { getsg(); while(~scanf("%d%d%d",&m,&n,&p) && m) { int sum=0; sum=sum^sg[m]^sg[n]^sg[p]; if(sum) printf("Fibo\n"); else printf("Nacci\n"); } return 0; }